Rank-pairing heaps

Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1463-1485
Number of pages23
JournalSIAM Journal on Computing
Volume40
Issue number6
DOIs
StatePublished - Dec 1 2011

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Algorithm
  • Amortized analysis
  • Data structure
  • Heap
  • Priority queue

Fingerprint Dive into the research topics of 'Rank-pairing heaps'. Together they form a unique fingerprint.

Cite this