TY - GEN
T1 - Rank-pairing heaps
AU - Haeupler, Bernhard
AU - Sen, Siddhartha
AU - Tarjan, Robert Endre
PY - 2009/11/11
Y1 - 2009/11/11
N2 - We introduce the rank-pairing heap, a heap (priority queue) implementation that combines the asymptotic efficiency of Fibonacci heaps with much of the simplicity of pairing heaps. Unlike all other heap implementations that match the bounds of Fibonacci heaps, our structure needs only one cut and no other structural changes per key decrease; the trees representing the heap can evolve to have arbitrary structure. Our initial experiments indicate that rank-pairing heaps perform almost as well as pairing heaps on typical input sequences and better on worst-case sequences.
AB - We introduce the rank-pairing heap, a heap (priority queue) implementation that combines the asymptotic efficiency of Fibonacci heaps with much of the simplicity of pairing heaps. Unlike all other heap implementations that match the bounds of Fibonacci heaps, our structure needs only one cut and no other structural changes per key decrease; the trees representing the heap can evolve to have arbitrary structure. Our initial experiments indicate that rank-pairing heaps perform almost as well as pairing heaps on typical input sequences and better on worst-case sequences.
UR - http://www.scopus.com/inward/record.url?scp=70350767562&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350767562&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-04128-0_59
DO - 10.1007/978-3-642-04128-0_59
M3 - Conference contribution
AN - SCOPUS:70350767562
SN - 3642041272
SN - 9783642041273
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 659
EP - 670
BT - Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
T2 - 17th Annual European Symposium on Algorithms, ESA 2009
Y2 - 7 September 2009 through 9 September 2009
ER -