Hollow Heaps
Authors:
Open Access
- 27 July 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 13 (3) , 1-27
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.Keywords
Funding Information
- Danmarks Grundforskningsfond (61061130540)
- German-Israeli Foundation for Scientific Research and Development (1161/2011)
- United States - Israel Binational Science Foundation (2012338)
- National Natural Science Foundation of China (61061130540)
- Israeli Centers of Research Excellence (Center No. 4/11)
- Natur og Univers, Det Frie Forskningsråd (12-126512)
- Israel Science Foundation (822-10 and 1841/14)
This publication has 20 references indexed in Scilit:
- Quake Heaps: A Simple Alternative to Fibonacci HeapsLecture Notes in Computer Science, 2013
- Strict fibonacci heaps2012
- Rank-Pairing HeapsSIAM Journal on Computing, 2011
- On the efficiency of pairing heaps and related data structuresJournal of the ACM, 1999
- Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computationCommunications of the ACM, 1988
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphsCombinatorica, 1986
- Implementation and Analysis of Binomial Queue AlgorithmsSIAM Journal on Computing, 1978
- Optimum branchingsJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967
- A note on two problems in connexion with graphsNumerische Mathematik, 1959