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]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Heap (data structure) — This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation. Example of a complete binary max heap In computer science, a heap is a specialized tree based data structure that satisfies the heap …   Wikipedia

  • Heap (Datenstruktur) — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Max-Heap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Min-Heap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Double-ended priority queue — Not to be confused with Double ended queue. A double ended priority queue (DEPQ)[1] is an abstract data type similar to a priority queue except that it allows for efficient removal of both the maximum and minimum element. It is a data structure… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • Dijkstra's algorithm — Not to be confused with Dykstra s projection algorithm. Dijkstra s algorithm Dijkstra s algorithm runtime Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

  • 2005 English cricket season (15–30 June) — See also: 2005 English cricket season The period of the 2005 English cricket season from 15 to 30 June started with another surprise Australia were beaten in their final NatWest Series warm up match by Somerset, or more specifically Graeme Smith… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.