Skip to main content
To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorHansen, Thomas D-
dc.contributor.authorKaplan, Haim-
dc.contributor.authorTarjan, Robert E-
dc.contributor.authorZwick, Uri-
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.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.relation.ispartofACM Transactions on Algorithmsen_US
dc.rightsAuthor's manuscripten_US
dc.titleHollow Heapsen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
HollowHeapsAlgorithms.pdf313.83 kBAdobe PDFView/Download

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