Rank-Pairing Heaps
Authors:
- Bernhard HaeuplerBHBernhard Haeupler
- Siddhartha SenSSSiddhartha Sen
- Robert E. TarjanRTRobert E. Tarjan
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (6) , 1463-1485
Abstract
We introduce the rank-pairing heap, an implementation of heaps that combines the asymptotic efficiency of Fibonacci heaps with much of the simplicity of pairing heaps. Other heap implementations that match the bounds of Fibonacci heaps do so by maintaining a balance condition on the trees representing the heap. In contrast to these structures but like pairing heaps, our trees can evolve to have arbitrary (unbalanced) structure. Also like pairing heaps, our structure requires at most one cut and no other restructuring per key decrease, in the worst case: the only changes that can cascade during a key decrease are changes in node ranks. Although our data structure is simple, its analysis is not.Keywords
This publication has 28 references indexed in Scilit:
- Two-tier relaxed heapsActa Informatica, 2008
- On the efficiency of pairing heaps and related data structuresJournal of the ACM, 1999
- Optimal purely functional priority queuesJournal of Functional Programming, 1996
- Trans-dichotomous algorithms for minimum spanning trees and shortest pathsJournal of Computer and System Sciences, 1994
- 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
- The pairing heap: A new form of self-adjusting heapAlgorithmica, 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