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.|
|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|
|Pages:||689 - 700|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||International Colloquium on Automata, Languages, and Programming|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.