Rank-pairing heaps

Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationAlgorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
Pages659-670
Number of pages12
DOIs
StatePublished - Nov 11 2009
Event17th Annual European Symposium on Algorithms, ESA 2009 - Copenhagen, Denmark
Duration: Sep 7 2009Sep 9 2009

Publication series

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

Other

Other17th Annual European Symposium on Algorithms, ESA 2009
CountryDenmark
CityCopenhagen
Period9/7/099/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