Gerth Stølting Brodal
Robert E. Tarjan
ABSTRACT
We present the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. We support make-heap, insert, find-min, meld and decrease-key in worst-case O(1) time, and delete and delete-min in worst-case O(lg n) time, where n is the size of the heap. The data structure uses linear space.
A previous, very complicated, solution achieving the same time bounds in the RAM model made essential use of arrays and extensive use of redundant counter schemes to maintain balance. Our solution uses neither. Our key simplification is to discard the structure of the smaller heap when doing a meld. We use the pigeonhole principle in place of the redundant counter mechanism.
Supplemental Material
- Gerth Stølting Brodal. Fast meldable priority queues. In Proc. 4th International Workshop Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, pages 282--290. Springer, 1995. Google Scholar
Digital Library
- Gerth Stølting Brodal. Worst-case efficient priority queues. InProc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 52--58. SIAM, 1996. Google ScholarDigital Library
- Svante Carlsson, J. Ian Munro, and Patricio V. Poblete. An implicit binomial queue with constant insertion time. In Proc. 1st Scandinavian Workshop on Algorithm Theory, volume 318 of Lecture Notes in Computer Science, pages 1--13. Springer, 1988. Google ScholarDigital Library
- Timothy M. Chan. Quake heaps: a simple alternative to Fibonacci heaps. Manuscript, 2009.Google Scholar
- Clark Allan Crane. Linear lists and priority queues as balanced binary trees. PhD thesis, Stanford University, Stanford, CA, USA, 1972.Google Scholar
- James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Communications of the ACM, 31(11):1343--1354, 1988. Google ScholarDigital Library
- Amr Elmasry. Layered heaps. In Proc. 9th Scandinavian Workshop on Algorithm Theory, volume 3111 of Lecture Notes in Computer Science, pages 212--222. Springer, 2004.Google ScholarCross Ref
- Amr Elmasry. Parameterized self-adjusting heaps. J. Algorithms, 52(2):103--119, 2004. Google ScholarDigital Library
- Amr Elmasry. Pairing heaps with o(log logn) decrease cost. In Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 471--476. SIAM, 2009. Google ScholarDigital Library
- Amr Elmasry. The violation heap: A relaxed Fibonacci-like heap. In Proc. 16th Annual International Conference on Computing and Combinatorics, volume 6196 of Lecture Notes in Computer Science, pages 479--488. Springer, 2010. Google ScholarDigital Library
- Amr Elmasry, Claus Jensen, and Jyrki Katajainen. On the power of structural violations in priority queues. In Proc. 13th Computing: The Australasian Theory Symposium., volume 65 of CRPIT, pages 45--53. Australian Computer Society, 2007. Google ScholarDigital Library
- Amr Elmasry, Claus Jensen, and Jyrki Katajainen. Two-tier relaxed heaps.Acta Informatica, 45(3):193--210, 2008. Google ScholarDigital Library
- Michael L. Fredman. On the efficiency of pairing heaps and related data structures.Journal of the ACM, 46(4):473--501, 1999. Google ScholarDigital Library
- Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator, and Robert Endre Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1(1):111--129, 1986. Google ScholarDigital Library
- Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596--615, 1987. Google ScholarDigital Library
- Bernhard Haeupler, Siddhartha Sen, and Robert Endre Tarjan. Rank-pairing heaps. In Proc. 17th Annual European Symposium on Algorithsm, volume 5757 of Lecture Notes in Computer Science, pages 659--670. Springer, 2009. SIAM Journal of Computing, to appear.Google ScholarCross Ref
- Peter Høyer. A general technique for implementation of efficient priority queues. In Proc. Third Israel Symposium on the Theory of Computing and Systems, pages 57--66, 1995. Google ScholarDigital Library
- Haim Kaplan and Robert E. Tarjan. New heap data structures. Technical report, Department of Computer Science, Princeton University, 1999.Google Scholar
- Haim Kaplan and Robert Endre Tarjan. Thin heaps, thick heaps.ACM Transactions on Algorithms, 4(1), 2008. Google ScholarDigital Library
- Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley, 1973.Google Scholar
- Gary L. Peterson. A balanced tree scheme for meldable heaps with updates. Technical Report GIT-ICS-87-23, School of Information and Computer Science, Georgia Institute of Technology, 1987.Google Scholar
- Seth Pettie. Towards a final analysis of pairing heaps. In Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pages 174--183. IEEE Computer Society, 2005. Google ScholarDigital Library
- Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting heaps.SIAM Journal of Computing, 15(1):52--69, 1986. Google ScholarDigital Library
- Jean Vuillemin. A data structure for manipulating priority queues.Communications of the ACM, 21(4):309--315, 1978. Google ScholarDigital Library
- John William Joseph Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347--348, 1964.Google Scholar
Index Terms
- Strict fibonacci heaps
Recommendations
Toward Optimal Self-Adjusting Heaps
We give a variant of the pairing heaps that achieves the following amortized costs: O(1) per find-min and insert, O(log log n) per decrease-key and meld, O(log n) per delete-min; where n is the number of elements in the resulting heap on which the ...
Hollow Heaps
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(...
Soft Heaps Simplified
In 1998, Chazelle [J. ACM, 47 (2000), pp. 1012--1027] introduced a new kind of meldable heap (priority queue) called the soft heap. Soft heaps trade accuracy for speed: the heap operations are allowed to increase the keys of certain items, thereby making ...
Reviews
Hui Liu
In computer science, heaps are special tree-based data structures, which are commonly manipulated with operations such as create-heap , insert , find-min , and delete . Heaps have interesting properties and are widely used in theory and applications, such as sorting, graph theory, and queueing. Fredman and Tarjan's Fibonacci heap is a special heap that can achieve O (1) amortized time bounds for almost all operations. The authors of this paper investigate Fibonacci heap implementation using pointers other than arrays. The authors first introduce basic concepts and four invariants and then analyze the properties of these invariants. The time complexities for commands such as make-heap , insert , find-min , meld , and decrease-key were O (1) in the worst case. The transformations used to link two nodes are introduced next. Heap operations implemented using transformations and invariants are verified. Data structures and transformations are represented at the abstract level, and pointer-based data structures and operations are presented in detail. The ideas used in this paper are helpful to other algorithm researchers. However, no experiment was presented. It would be interesting to know the performance improvement of this new implementation. The main contribution of this paper is that the authors are the first to present pointer-based Fibonacci heap implementation. The time bounds for almost all the operations achieved O (1) in the worst case. The concepts and methods introduced in this paper are also interesting. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments