Skip to main content
To refer to this page use:
Abstract: amortized time. Hollow heaps are by far the simplest structure to achieve this. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations, and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.
Publication Date: 2015
Citation: Hansen, Thomas Dueholm, Haim Kaplan, Robert E. Tarjan, and Uri Zwick. "Hollow Heaps." In International Colloquium on Automata, Languages, and Programming (2015): pp. 689-700. doi:10.1007/978-3-662-47672-7_56
DOI: 10.1007/978-3-662-47672-7_56
Pages: 689 - 700
Type of Material: Conference Article
Journal/Proceeding Title: International Colloquium on Automata, Languages, and Programming
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.