DIMACS TR: 97-52

Pairing Heaps Are Suboptimal

Author: Michael L. Fredman


Pairing heaps were introduced as a self-adjusting alternative to Fibonacci heaps. They provably enjoy log n amortized costs for the standard heap operations. Although it has not been verified that pairing heaps perform the decrease key operation in constant amortized time, this has been conjectured and extensive experimental evidence supports this conjecture. Moreover, pairing heaps have been observed to be superior to Fibonacci heaps in practice. However, as demonstrated in this paper, pairing heaps do not accommodate decrease key operations in constant amortized time.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-52.ps.gz
DIMACS Home Page