The pairing heap: A new form of self-adjusting heap

Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

108 Scopus citations

Abstract

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called the Fibonacci heap. Although theoretically efficient, Fibonacci heaps are complicated to implement and not as fast in practice as other kinds of heaps. In this paper we describe a new form of heap, called the pairing heap, intended to be competitive with the Fibonacci heap in theory and easy to implement and fast in practice. We provide a partial complexity analysis of pairing heaps. Complete analysis remains an open problem.

Original languageEnglish (US)
Pages (from-to)111-129
Number of pages19
JournalAlgorithmica
Volume1
Issue number1
DOIs
StatePublished - Mar 1 1986

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The pairing heap: A new form of self-adjusting heap'. Together they form a unique fingerprint.

Cite this