Skip to main content
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr19n9r
Abstract: We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take O(1) time, worst case as well as amortized; delete and delete-min take O(log n) amortized time on a heap of n items. Hollow heaps are the simplest structure to achieve these bounds. 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: Jul-2017
Citation: Hansen, Thomas Dueholm, Haim Kaplan, Robert E. Tarjan, and Uri Zwick. "Hollow Heaps." ACM Transactions on Algorithms 13, no. 3 (2017): 42:1-42:27. doi:10.1145/3093240
DOI: 10.1145/3093240
ISSN: 1549-6325
EISSN: 1549-6333
Pages: 42:1 - 42:27
Type of Material: Journal Article
Journal/Proceeding Title: ACM Transactions on Algorithms
Version: Author's manuscript



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