ABSTRACT
Strengths: Experimental studies [142, 104] have shown that, in practice, the pairing heap yields the best performance for many graph algorithms that rely upon a priority queue. (Chapter 56 discusses the greedy tree builder, from which these algorithms are derived.) In particular, Experiments by Moret and Shapiro [116] demonstrated that using a pairing heap within Prim’s minimum spanning algorithm leads to a more efficient solution that using a binary heap, Fibonacci heap, or a variety of other priority queue data structures. Also, a pairing heap is a relatively simple, easily implemented, data structure. It is conjectured that the amortized cost of increasing the priority of an element is O(log log n), although the best proven bound is O(log n).
