# Hollow Heaps

## Author(s): Hansen, Thomas D; Kaplan, Haim; Tarjan, Robert E; Zwick, Uri

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