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.[1]
Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. 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):
find-min: simply return the top element of the heap.
meld: compare the two root elements, the smaller remains the root of the result, the larger element and its subtree is appended as a child of this root.
insert: create a new heap for the inserted element and meld into the original heap.
decrease-key (optional): remove the subtree rooted at the key to be decreased, replace the key with a smaller key, then meld the result back into the heap.
delete-min: remove the root and do repeated melds of its subtrees until one tree remains. Various merging strategies are employed.
The analysis of pairing heaps' time complexity was initially inspired by that of splay trees.[1]
The amortized time per delete-min is O(log n), and the operations find-min, meld, and insert run in O(1) time.[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. Initially, the time complexity of this operation was conjectured on empirical grounds to be O(1),[4] but Fredman proved that the amortized time per decrease-key is at least for some sequences of operations.[5]
Using a different amortization argument, Pettie then proved that insert, meld, and decrease-key all run in amortized time, which is .[6]
Elmasry later introduced elaborations of pairing heaps (lazy, consolidate) for which decrease-key runs in amortized time and other operations have optimal amortized bounds,[7][8] but no tight bound is known for the original data structure.[3][6]
Although the asymptotic performance of pairing heaps is worse than other priority queue algorithms such as Fibonacci heaps, which perform decrease-key in amortized time, the performance in practice is excellent. Jones[9]
and Larkin, Sen, and Tarjan[10]
conducted experiments on pairing heaps and other heap data structures. They concluded that d-ary heaps such as binary heaps are faster than all other heap implementations when the decrease-key operation is not needed (and hence there is no need to externally track the location of nodes in the heap), but that when decrease-key is needed pairing heaps are often faster than d-ary heaps and almost always faster than other pointer-based heaps, including data structures like Fibonacci heaps that are theoretically more efficient. 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.
^ abFredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). "The pairing heap: a new form of self-adjusting heap" (PDF). Algorithmica. 1 (1–4): 111–129. doi:10.1007/BF01840439. S2CID 23664143.
^Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox(PDF). Springer. p. 231.
^ abCite error: The named reference Iacono was invoked but never defined (see the help page).
^
Stasko, John T.; Vitter, Jeffrey S. (1987), "Pairing heaps: experiments and analysis" (PDF), Communications of the ACM, 30 (3): 234–249, CiteSeerX 10.1.1.106.2988, doi:10.1145/214748.214759, S2CID 17811811
^Fredman, Michael L. (1999). "On the efficiency of pairing heaps and related data structures" (PDF). Journal of the ACM. 46 (4): 473–501. doi:10.1145/320211.320214. S2CID 16115266. Archived from the original (PDF) on 2011-07-21. Retrieved 2011-05-03.
^ abPettie, Seth (2005), "Towards a final analysis of pairing heaps" (PDF), Proc. 46th Annual IEEE Symposium on Foundations of Computer Science(PDF), pp. 174–183, doi:10.1109/SFCS.2005.75, ISBN 0-7695-2468-0, S2CID 2717102
^Elmasry, Amr (2009), "Pairing heaps with O(log log n) decrease cost" (PDF), Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 471–476, CiteSeerX 10.1.1.502.6706, doi:10.1137/1.9781611973068.52
^Elmasry, Amr (November 2017). "Toward Optimal Self-Adjusting Heaps". ACM Transactions on Algorithms. 13 (4): 1–14. doi:10.1145/3147138. S2CID 1182235.
^Jones, Douglas W. (1986). "An empirical comparison of priority-queue and event-set implementations". Communications of the ACM. 29 (4): 300–311. CiteSeerX 10.1.1.117.9380. doi:10.1145/5684.5686. S2CID 43650389.
^Larkin, Daniel H.; Sen, Siddhartha; Tarjan, Robert E. (2014), "A back-to-basics empirical study of priority queues", Proceedings of the 16th Workshop on Algorithm Engineering and Experiments, pp. 61–72, arXiv:1403.0252, doi:10.1137/1.9781611973198.7, ISBN 978-1-61197-319-8, S2CID 15216766
^Chen, Mo; Chowdhury, Rezaul Alam; Ramachandran, Vijaya; Roche, David Lan; Tong, Lingling (12 October 2007). Priority Queues and Dijkstra's Algorithm(PDF) (Technical report). University of Texas. TR-07-54.{{cite tech report}}: CS1 maint: date and year (link)
A pairingheap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael...
A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues.: 162–163 The...
in other structures, such as the binary heap, binomial heap, pairingheap, Brodal queue and rank-pairingheap. Although the total running time of a sequence...
science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports...
elements. Variants of the basic heap data structure such as pairingheaps or Fibonacci heaps can provide better bounds for some operations. Alternatively...
In computer science, a skew binomial heap (or skew binomial queue) is a variant of the binomial heap that supports constant-time insertion operations...
Imogen Jennifer Jane Heap (/ˈɪmədʒən ˈhiːp/ IM-ə-jən HEEP; born 9 December 1977) is a British musician, singer, songwriter and record producer. Her work...
1017/s095679680000201x Iacono, John (2000), "Improved upper bounds for pairingheaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture...
Fibonacci heap is a priority queue data structure with low worst case time bounds. It matches the amortized time bounds of the Fibonacci heap in the worst...
maintain the heap property. Examples of mergeable heap data structures include: Binomial heap Fibonacci heap Leftist tree Pairingheap Skew heap A more complete...
1017/s095679680000201x Iacono, John (2000), "Improved upper bounds for pairingheaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture...
implementation, others do exist. These are: Leftist heap Binomial heap Fibonacci HeapPairingheap Skew heap A. Gambin and A. Malinowski. 1998. Randomized Meldable...
Septimus Heap is a series of children's fantasy novels featuring a protagonist of the same name written by English author Angie Sage. In all, it features...
which two players take turns removing (or "nimming") objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may...
This article catalogs the key characters from the books in the Septimus Heap series by Angie Sage. These include the books Magyk, Flyte, Physik, Queste...
maximum. Also like heapsort, the priority queue is an implicit heap data structure (a heap-ordered implicit binary tree), which occupies a prefix of the...
Daniel James Macdonnell Heap (September 24, 1925 – April 25, 2014) was a Canadian activist and politician. Heap served as a Member of Parliament with...
A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements (keys associated with priorities)...
cards placed side by side. May or may not be overlapped. rubbish heap, rubbish-heap See wastepile. sequence, ascending sequence, descending sequence A...