Pairing heap
From Wikipedia, the free encyclopedia
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):
- 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.
[edit] 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.
