Information about Pairing Heap
Pairing heaps are a type of heap data structure with relatively simple implementation, excellent practical amortized performance (particularly for applications where heaps must be merged). However it has proven very difficult to analyse pairing heaps and prove theoretical bounds for them.
Pairing heaps are heap ordered multiway trees. Describing the various heap operations is relatively simple (in the following we assume a min-heap):
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 for which the root is the key to be decreased and merge with the heap.
- delete-min: remove the root and merge its subtrees. Various strategies are employed.
References
- Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator, and Robert Endre Tarjan, The Pairing Heap: A New Form of Self-Adjusting Heap, Algorithmica, 1(1):111-129, 1986.
External links
heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B).
..... Click the link for more information.
..... Click the link for more information.
data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data type.
..... Click the link for more information.
..... Click the link for more information.
amortized analysis refers to finding the average running time per operation over a worst-case sequence of operations. Amortized analysis differs from average-case performance in that probability is not involved; amortized analysis guarantees the time per operation over
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
