A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986.
They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm,[2] and support the following operations (assuming a min-heap): The analysis of pairing heaps' time complexity was initially inspired by that of splay trees.
[3] When a decrease-key operation is added as well, determining the precise asymptotic running time of pairing heaps has turned out to be difficult.
[5] Using a different amortization argument, Pettie then proved that insert, meld, and decrease-key all run in
[6] Elmasry later introduced elaborations of pairing heaps (lazy, consolidate) for which decrease-key runs in
Chen et al.[11] examined priority queues specifically for use with Dijkstra's algorithm and concluded that in normal cases using a d-ary heap without decrease-key (instead duplicating nodes on the heap and ignoring redundant instances) resulted in better performance, despite the inferior theoretical performance guarantees.
The following description assumes a purely functional heap that does not support the decrease-key operation.
Alternatively, the previous-pointer can be omitted by letting the last child point back to the parent, if a single boolean flag is added to indicate "end of list".
The standard strategy first melds the subheaps in pairs (this is the step that gave this data structure its name) from left to right and then melds the resulting list of heaps from right to left: This uses the auxiliary function merge-pairs: That this does indeed implement the described two-pass left-to-right then right-to-left merging strategy can be seen from this reduction: Here are time complexities[12] of various heap data structures.