Pairing Heaps are Sub-optimal

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. 1 Introduction Pairing heaps were introduced [1] as a self-adjusting alternative to Fibonacci heaps [2]. They are easy to code and provably enjoy log n amortized costs for the standard heap operations. Although it had not been verified that pairing heaps perform the decrease key operation in constant amortized time (the raison d'etre of Fibonacci heaps), this has been conjectured [1] and extensive experimental eviden..