Rank-pairing heaps

Bernhard Haeupler; Siddhartha Sen; Robert E. Tarjan

doi:10.1007/978-3-642-04128-0_59

Rank-pairing heaps

Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
Pages	659-670
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-04128-0_59
State	Published - 2009
Event	17th Annual European Symposium on Algorithms, ESA 2009 - Copenhagen, Denmark Duration: Sep 7 2009 → Sep 9 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5757 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	17th Annual European Symposium on Algorithms, ESA 2009
Country/Territory	Denmark
City	Copenhagen
Period	9/7/09 → 9/9/09

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-04128-0_59

Cite this

@inproceedings{986e18eb1e95414e9adf93cda62b1da2,

title = "Rank-pairing heaps",

abstract = "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.",

author = "Bernhard Haeupler and Siddhartha Sen and Tarjan, {Robert E.}",

year = "2009",

doi = "10.1007/978-3-642-04128-0_59",

language = "English (US)",

isbn = "3642041272",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "659--670",

booktitle = "Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings",

note = "17th Annual European Symposium on Algorithms, ESA 2009 ; Conference date: 07-09-2009 Through 09-09-2009",

}

Haeupler, B, Sen, S & Tarjan, RE 2009, Rank-pairing heaps. in Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5757 LNCS, pp. 659-670, 17th Annual European Symposium on Algorithms, ESA 2009, Copenhagen, Denmark, 9/7/09. https://doi.org/10.1007/978-3-642-04128-0_59

Rank-pairing heaps. / Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E.
Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings. 2009. p. 659-670 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5757 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Rank-pairing heaps

AU - Haeupler, Bernhard

AU - Sen, Siddhartha

AU - Tarjan, Robert E.

PY - 2009

Y1 - 2009

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 -

Rank-pairing heaps

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this