Pairing heap

Pairing heaps are a type of heap data structure with relatively simple implementation and excellent practical amortized performance. However, it has proven very difficult to determine the precise asymptotic running time of pairing heaps.

Pairing heaps are heap ordered multiway trees. Describing the various heap operations is relatively simple (in the following we assume a min-heap):

* "find-min": simply return the top element of the heap.
* "merge": compare the two root elements, the smaller remains the root of the result and the subtree of the larger element is appended as a child of this root.
* "insert": create a new heap for the inserted element and "merge" into the original heap.
* "decrease-key": remove the subtree rooted at the key to be decreased then "merge" it with the heap.
* "delete-min": remove the root and "merge" its subtrees. Various strategies are employed.

The amortized time per "delete-min" is $O(log\; n)$.Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator, and Robert Endre Tarjan. The Pairing He
] The operations "find-min", "merge", and "insert" take $O(1)$ amortized timeJohn Iacono. [http://www.springerlink.com/content/yv91h55qw75anfkv/ Improved upper bounds for pairing heaps] . In Proceedings 7th Scandinavian Workshop on Algorithm Theory, LNCS 1851, pages 63--77, 2000.] and "decrease-key" takes $2^\{O(sqrt\{loglog\; n\})\}$ amortized time.Seth Pettie. [http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.75 Towards a final analysis of pairing heaps] . In Proceedings 46th Annual IEEE Symposium on Foundations of Computer Science, pages 174--183, 2005.] Fredman proved that the amortized time per "decrease-key" is at least $Omega(loglog\; n)$.Michael L. Fredman. [http://doi.acm.org/10.1145/320211.320214 On the efficiency of pairing heaps and related data structures] . "J. ACM" 46(4):473--501, 1999.] That is, they are less efficient than Fibonacci heaps, which perform "decrease-key" in $O(1)$ amortized time.

Stasko and VitterJohn T. Stasko and Jeffrey S. Vitter. [http://doi.acm.org/10.1145/214748.214759 Pairing Heaps: Experiments and Analysis] . "Commun. ACM" 30(3):234--249, 1987.] and Moret and ShapiroBernard M. E. Moret, Henry D. Shapiro. [http://www.springerlink.com/content/d7rq41v0477rl567/ An Empirical Analysis of Algorithms for Constructing a Minimum Spanning Tree] . Proceedings 2nd Workshop on Algorithms and Data Structures, pages 400--411, 1991] conducted experiments on pairing heaps and other heap data structures. They concluded that the pairing heap is as fast as, and often faster than, other efficient data structures like the binary heaps.

References

External links

* [http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c13/pairing.htm Sartaj Sahni's pairing heaps page]