@article{4b8e93033190490dab96d9c247fc105c,
title = "Hollow heaps",
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.",
keywords = "Amortized analysis, Data structures, Heaps, Priority queues",
author = "Hansen, {Thomas Dueholm} and Haim Kaplan and Tarjan, {Robert E.} and Uri Zwick",
note = "Funding Information: Work of Thomas Dueholm Hansen supported by The Danish Council for Independent Research | Natural Sciences (grant no. 12-126512); and the Sino-Danish Center for the Theory of Interactive Computation, funded by the Danish National Research Foundation and the National Science Foundation of China (under the grant 61061130540). Work of Haim Kaplan supported by the Israel Science Foundation grants no. 822-10 and 1841/14, the German-Israeli Foundation for Scientific Research and Development (GIF) grant no. 1161/2011, and the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11). Work of Uri Zwick supported by BSF grant no. 2012338 and by The Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11). Publisher Copyright: {\textcopyright} 2017 ACM.",
year = "2017",
month = jul,
doi = "10.1145/3093240",
language = "English (US)",
volume = "13",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery (ACM)",
number = "3",
}