DIMACS TR: 97-52
Pairing Heaps Are Suboptimal
Author: Michael L. Fredman
ABSTRACT
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