COCOA Talk: 99-04

Speaker: John Iacono

Pairing heaps are a self adjusting form of heap which are closely
related to splay trees. They are easy to implement and empirically
perform well. They are in widespread use, appearing in the GNU C++
Library, and in introductory undergraduate texts. Pairing heaps were
designed to compete with Fibonacci Heaps, which are theoreticly
efficient, but perform poorly in real life due to the large constants
inherent in their implementation. The complete analysis of pairing
heaps has remained elusive, and it was unknown until fairly recently
whether or not Fibonacci heaps and Pairing heaps had the same
asymptotic amortized performance (they do not). In this talk, one
recent positive result will be presented: Pairing heaps support
insertions in constant amortized time. This improves the previous
analysis of O(log n) amortized time per insert.

DIMACS Home Page