To refer to this page use:
|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.|
|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|
|Pages:||42:1 - 42:27|
|Type of Material:||Journal Article|
|Journal/Proceeding Title:||ACM Transactions on Algorithms|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.