To refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1fc1s| 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.