# 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
DC FieldValueLanguage
dc.contributor.authorHansen, Thomas D-
dc.contributor.authorKaplan, Haim-
dc.contributor.authorTarjan, Robert E-
dc.contributor.authorZwick, Uri-
dc.date.accessioned2021-10-08T19:47:33Z-
dc.date.available2021-10-08T19:47:33Z-
dc.date.issued2017-07en_US
dc.identifier.citationHansen, 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/3093240en_US
dc.identifier.issn1549-6325-
dc.identifier.urihttps://arxiv.org/pdf/1510.06535.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr19n9r-
dc.description.abstractWe 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.en_US
dc.format.extent42:1 - 42:27en_US
dc.language.isoen_USen_US
dc.relation.ispartofACM Transactions on Algorithmsen_US
dc.rightsAuthor's manuscripten_US
dc.titleHollow Heapsen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1145/3093240-
dc.identifier.eissn1549-6333-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat