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 | |
| State | Published - Nov 11 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 | Denmark |
| City | Copenhagen |
| Period | 9/7/09 → 9/9/09 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)
Fingerprint Dive into the research topics of 'Rank-pairing heaps'. Together they form a unique fingerprint.
Cite this
Haeupler, B., Sen, S., & Tarjan, R. E. (2009). Rank-pairing heaps. In Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings (pp. 659-670). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5757 LNCS). https://doi.org/10.1007/978-3-642-04128-0_59