Improved Upper Bounds for Pairing Heaps
arXiv:1110.4428
Abstract
Pairing heaps are shown to have constant amortized time Insert and Meld, thus showing that pairing heaps have the same amortized runtimes as Fibonacci heaps for all operations but Decrease-key.
Preliminary version appeared at the Seventh Scandinavian Workshop on Algorithm Theory (SWAT 2000)