Pairing heap
From Wikipedia, the free encyclopedia
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(logn).[1] The operations find-min, merge, and insert take O(1) amortized time[2] and decrease-key takes 
amortized time.[3] Fredman proved that the amortized time per decrease-key is at least Ω(loglogn).[4] That is, they are less efficient than Fibonacci heaps, which perform decrease-key in O(1) amortized time.
Stasko and Vitter[5] and Moret and Shapiro[6] 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.
[edit] References
- ^ Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986), "The pairing heap: a new form of self-adjusting heap", Algorithmica 1 (1): 111–129, doi:.
- ^ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, 1851, Springer-Verlag, pp. 63–77, doi:.
- ^ Pettie, Seth (2005), "Towards a final analysis of pairing heaps", Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174–183, doi:.
- ^ Fredman, Michael L. (1999), "On the efficiency of pairing heaps and related data structures", Journal of the ACM 46 (4): 473–501, doi:.
- ^ Stasko, John T.; Vitter, Jeffrey S. (1987), "Pairing heaps: experiments and analysis", Communications of the ACM 30 (3): 234–249, doi:.
- ^ Moret, Bernard M. E.; Shapiro, Henry D. (1991), "An empirical analysis of algorithms for constructing a minimum spanning tree", Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 519, Springer-Verlag, pp. 400–411, doi:.
