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(logn) 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.
Original language | English (US) |
---|---|
Article number | 42 |
Journal | ACM Transactions on Algorithms |
Volume | 13 |
Issue number | 3 |
DOIs | |
State | Published - Jul 2017 |
All Science Journal Classification (ASJC) codes
- Mathematics (miscellaneous)
Keywords
- Amortized analysis
- Data structures
- Heaps
- Priority queues