471:
A pairing heap is either an empty heap, or a pairing tree consisting of a root element and a possibly empty list of pairing trees. The heap ordering property requires that parent of any node is no greater than the node itself. The following description assumes a purely functional heap that does not
615:
The only non-trivial fundamental operation is the deletion of the minimum element from the heap. This requires performing repeated melds of its children until only one tree remains. The standard strategy first melds the subheaps in pairs (this is the step that gave this data structure its name)
505:
with an additional pointer to a node's parent (which represents its previous sibling or actual parent for the leftmost sibling). 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". This
519:
Melding with an empty heap returns the other heap, otherwise a new heap is returned that has the minimum of the two root elements as its root element and just adds the heap with the larger root to the list of subheaps:
158:
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
1718:
280:
459:
that are theoretically more efficient. Chen et al. examined priority queues specifically for use with
Dijkstra's algorithm and concluded that in normal cases using a d-ary heap without
443:
amortized time, the performance in practice is excellent. Jones and Larkin, Sen, and Tarjan conducted experiments on pairing heaps and other heap data structures. They concluded that
501:: a pointer to the node's first child, one to its next sibling, and one to its previous sibling (or, for the leftmost sibling, to its parent). It can also be viewed as a variant of a
1660:
1731:
Brodal queues and strict
Fibonacci heaps achieve optimal worst-case complexities for heaps. They were first described as imperative data structures. The Brodal-Okasaki queue is a
401:
213:
360:
2762:
2633:
315:
441:
463:(instead duplicating nodes on the heap and ignoring redundant instances) resulted in better performance, despite the inferior theoretical performance guarantees.
2458:
79:: 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.
1975:
455:
is needed pairing heaps are often faster than d-ary heaps and almost always faster than other pointer-based heaps, including data structures like
565:
The easiest way to insert an element into a heap is to meld the heap with a new heap containing just this element and an empty list of subheaps:
2838:
2441:
2253:
1768:
39:
502:
675:
That this does indeed implement the described two-pass left-to-right then right-to-left merging strategy can be seen from this reduction:
2948:
1825:
2895:
2692:
2582:
2339:
2296:
2062:
1898:
2943:
2106:
710:
2914:
686:, meld(meld(H5, H6), merge-pairs()))) # meld H5 and H6 to H56, then the rest of the list => meld(H12, meld(H34, meld(
1609:). Applied to skew binomial heaps, it yields Brodal-Okasaki queues, persistent heaps with optimal worst-case complexities.
451:
operation is not needed (and hence there is no need to externally track the location of nodes in the heap), but that when
678:
merge-pairs() => meld(meld(H1, H2), merge-pairs()) # meld H1 and H2 to H12, then the rest of the list => meld(
2754:
1665:
2329:
230:
1921:
682:, meld(meld(H3, H4), merge-pairs())) # meld H3 and H4 to H34, then the rest of the list => meld(H12, meld(
2373:
2290:
1732:
1558:
2669:. FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183.
2491:
717:
indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "
2854:
2799:
1829:
2276:
Chen, Mo; Chowdhury, Rezaul Alam; Ramachandran, Vijaya; Roche, David Lan; Tong, Lingling (12 October 2007).
1621:
406:
Although the asymptotic performance of pairing heaps is worse than other priority queue algorithms such as
95:(optional): remove the subtree rooted at the key to be decreased, replace the key with a smaller key, then
2816:
2771:
2670:
2473:
2382:
2186:
2111:
1936:
1876:
690:, H7))) # switch direction, meld the last two resulting heaps, giving H567 => meld(H12, meld(H34,
365:
177:
2602:
1397:
55:
24:
2006:
1283:
2542:
Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues",
2321:
2177:
Jones, Douglas W. (1986). "An empirical comparison of priority-queue and event-set implementations".
2821:
2776:
2625:
2478:
2191:
2116:
2086:
1941:
1881:
324:
2879:
2675:
2598:
2387:
215:
for some sequences of operations. Using a different amortization argument, Pettie then proved that
63:
2259:
2231:
2204:
2159:
2068:
1998:
1954:
1866:
1803:
1032:
498:
2918:
285:
2924:
2891:
2834:
2688:
2578:
2437:
2400:
2335:
2249:
2058:
1894:
506:
achieves a more compact structure at the expense of a constant overhead factor per operation.
2368:
2277:
497:, can be achieved using three pointers per node, by representing the children of a node by a
2883:
2826:
2781:
2728:
2680:
2642:
2551:
2483:
2429:
2392:
2317:
2241:
2196:
2151:
2121:
2050:
1990:
1946:
1886:
1795:
2815:. Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184.
1780:
2746:
2621:
1971:
1764:
417:
167:
35:
2360:
1917:
1772:
1340:
734:
456:
407:
317:. Elmasry later introduced elaborations of pairing heaps (lazy, consolidate) for which
59:
43:
27:
2661:
2041:
2034:
1865:, Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77,
2937:
2803:
2750:
2709:
2570:
2487:
2421:
2364:
2223:
2139:
1821:
1776:
970:
51:
47:
2263:
2208:
2002:
1958:
1807:
1091:
2928:
2163:
2072:
1448:
907:
616:
from left to right and then melds the resulting list of heaps from right to left:
698:) # finally, meld the first pair with the result of merging the rest =>
113:
The analysis of pairing heaps' time complexity was initially inspired by that of
109:
of its subtrees until one tree remains. Various merging strategies are employed.
2713:
1913:
1857:
1853:
766:
490:
362:
amortized time and other operations have optimal amortized bounds, but no tight
2858:
2807:
2125:
2556:
2325:
2245:
1535:) time (where both complexities can be amortized). Another algorithm achieves
444:
114:
2404:
447:
such as binary heaps are faster than all other heap implementations when the
2830:
2755:"Fibonacci heaps and their uses in improved network optimization algorithms"
2433:
1890:
1152:
829:
62:. They are considered a "robust choice" for implementing such algorithms as
31:
694:)) # meld the last two resulting heaps, giving H34567 => meld(H12,
2646:
1994:
1950:
2684:
2228:
Proceedings of the 16th
Workshop on Algorithm Engineering and Experiments
2054:
2785:
2515:
1799:
2732:
2200:
2913:
Louis
Wasserman discusses pairing heaps and their implementation in
2396:
2155:
2043:
Proc. 46th Annual IEEE Symposium on
Foundations of Computer Science
2236:
1871:
2626:"On the Efficiency of Pairing Heaps and Related Data Structures"
1976:"On the efficiency of pairing heaps and related data structures"
2226:(2014), "A back-to-basics empirical study of priority queues",
2459:"Average Case Analysis of Heap Building by Repeated Insertion"
66:, and support the following operations (assuming a min-heap):
30:
with relatively simple implementation and excellent practical
571:
insert(elem: Elem, heap: PairingHeap) -> PairingHeap
2866:
Proc. 7th Annual ACM-SIAM Symposium on
Discrete Algorithms
1735:
data structure achieving the same optimum, except that
1511:
is the operation of building a heap from a sequence of
2355:
2353:
2351:
526:meld(heap1, heap2: PairingHeap) -> PairingHeap
1781:"The pairing heap: a new form of self-adjusting heap"
1668:
1624:
420:
368:
327:
288:
233:
180:
622:delete-min(heap: PairingHeap) -> PairingHeap
2516:"Binomial Heap | Brilliant Math & Science Wiki"
1859:
1856:(2000), "Improved upper bounds for pairing heaps",
550:Heap(heap1.elem, heap2 :: heap1.subheaps)
2763:Journal of the Association for Computing Machinery
2634:Journal of the Association for Computing Machinery
2285:(Technical report). University of Texas. TR-07-54.
1712:
1654:
713:of various heap data structures. The abbreviation
435:
395:
354:
309:
274:
207:
2537:
2535:
2416:
2414:
1831:Algorithms and Data Structures: The Basic Toolbox
1553:
1551:
1549:
85:: create a new heap for the inserted element and
1565:), a generic transformation reduces the cost of
482:PairingTree = Heap(elem: Elem, subheaps: List])
403:bound is known for the original data structure.
649:merge-pairs(list: List]) -> PairingHeap
557:Heap(heap2.elem, heap1 :: heap2.subheaps)
2886:(2004). "7.3.6. Bottom-Up Heap Construction".
1713:{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}
587:simply returns the root element of the heap:
275:{\displaystyle O(2^{2{\sqrt {\log \log n}}})}
8:
1368:
1359:
1311:
1302:
1254:
1241:
1215:
1202:
1193:
1184:
1171:
1125:
1110:
1005:
900:
887:
874:
861:
848:
714:
73:: simply return the top element of the heap.
2334:(1st ed.). MIT Press and McGraw-Hill.
2035:"Towards a final analysis of pairing heaps"
593:find-min(heap: PairingHeap) -> Elem
1727:
1725:
672:meld(meld(list, list), merge-pairs(list))
2820:
2775:
2674:
2663:Towards a Final Analysis of Pairing Heaps
2555:
2477:
2386:
2235:
2190:
2115:
1940:
1922:"Pairing heaps: experiments and analysis"
1880:
1870:
1683:
1679:
1667:
1623:
737:. Names of operations assume a min-heap.
419:
367:
326:
287:
248:
244:
232:
179:
2573:(1998). "10.2. Structural Abstraction".
2457:Hayward, Ryan; McDiarmid, Colin (1991).
2279:Priority Queues and Dijkstra's Algorithm
2028:
2026:
1848:
1846:
1844:
739:
2312:
2310:
2308:
2306:
1751:
1501:
2888:Data Structures and Algorithms in Java
2859:"Worst-Case Efficient Priority Queues"
2426:Data Structures and Network Algorithms
2288:
1759:
1757:
1755:
2708:Haeupler, Bernhard; Sen, Siddhartha;
2140:"Toward Optimal Self-Adjusting Heaps"
1655:{\displaystyle \Omega (\log \log n),}
1515:unsorted elements. It can be done in
7:
2222:Larkin, Daniel H.; Sen, Siddhartha;
1593:(1) time (amortized, if the cost of
503:Left-child right-sibling binary tree
396:{\displaystyle \Theta (\log \log n)}
208:{\displaystyle \Omega (\log \log n)}
546:heap1.elem < heap2.elem
489:A pointer-based implementation for
170:proved that the amortized time per
58:, and can be considered simplified
2890:(3rd ed.). pp. 338–341.
2577:(1st ed.). pp. 158–162.
1625:
486:PairingHeap = Empty | PairingTree
369:
181:
105:: remove the root and do repeated
14:
2575:Purely Functional Data Structures
2544:Journal of Functional Programming
639:This uses the auxiliary function
2107:Symposium on Discrete Algorithms
1577:is the sum of the old costs of
2424:(1983). "3.3. Leftist heaps".
2144:ACM Transactions on Algorithms
2138:Elmasry, Amr (November 2017).
1704:
1672:
1646:
1628:
430:
424:
390:
372:
355:{\displaystyle O(\log \log n)}
349:
331:
304:
292:
269:
237:
202:
184:
99:the result back into the heap.
16:Variant of heap data structure
1:
2295:: CS1 maint: date and year (
2488:10.1016/0196-6774(91)90027-v
2105:Proc. 20th Annual ACM-SIAM
636:merge-pairs(heap.subheaps)
50:in 1986. Pairing heaps are
34:performance, introduced by
2965:
2919:The Monad Reader, Issue 16
2331:Introduction to Algorithms
2126:10.1137/1.9781611973068.52
661:length(list) == 1
653:length(list) == 0
2949:Amortized data structures
2747:Fredman, Michael Lawrence
2622:Fredman, Michael Lawrence
2557:10.1017/s095679680000201x
2374:SIAM Journal on Computing
2246:10.1137/1.9781611973198.7
2179:Communications of the ACM
1929:Communications of the ACM
575:meld(Heap(elem, ), heap)
310:{\displaystyle o(\log n)}
282:amortized time, which is
117:. The amortized time per
1837:. Springer. p. 231.
1573:, while the new cost of
705:Summary of running times
2944:Heaps (data structures)
2831:10.1145/2213977.2214082
2802:; Lagogiannis, George;
2434:10.1137/1.9781611970265
2361:Sleator, Daniel Dominic
1891:10.1007/3-540-44985-X_5
538:heap2 is Empty
530:heap1 is Empty
89:into the original heap.
2809:Strict Fibonacci heaps
2800:Brodal, Gerth Stølting
2369:"Self-Adjusting Heaps"
1714:
1656:
1561:heaps (not supporting
626:heap is Empty
597:heap is Empty
437:
397:
356:
311:
276:
209:
2660:Pettie, Seth (2005).
2647:10.1145/320211.320214
2322:Leiserson, Charles E.
2085:Elmasry, Amr (2009),
2033:Pettie, Seth (2005),
1995:10.1145/320211.320214
1951:10.1145/214748.214759
1715:
1657:
438:
398:
357:
312:
277:
210:
132:, and the operations
2880:Goodrich, Michael T.
2714:"Rank-pairing heaps"
2685:10.1109/SFCS.2005.75
2365:Tarjan, Robert Endre
2110:, pp. 471–476,
2087:"Pairing heaps with
2055:10.1109/SFCS.2005.75
2049:, pp. 174–183,
1666:
1622:
436:{\displaystyle O(1)}
418:
366:
325:
286:
231:
178:
64:Prim's MST algorithm
2786:10.1145/28869.28874
2604:Theory of 2–3 Heaps
1972:Fredman, Michael L.
1765:Fredman, Michael L.
1543:) for binary heaps.
2428:. pp. 38–42.
2230:, pp. 61–72,
1983:Journal of the ACM
1918:Vitter, Jeffrey S.
1800:10.1007/BF01840439
1773:Sleator, Daniel D.
1710:
1652:
499:doubly-linked list
433:
393:
352:
307:
272:
205:
2921:(pp. 37–52).
2884:Tamassia, Roberto
2840:978-1-4503-1245-5
2804:Tarjan, Robert E.
2751:Tarjan, Robert E.
2733:10.1137/100785351
2721:SIAM J. Computing
2712:(November 2011).
2710:Tarjan, Robert E.
2443:978-0-89871-187-5
2367:(February 1986).
2326:Rivest, Ronald L.
2318:Cormen, Thomas H.
2255:978-1-61197-319-8
2224:Tarjan, Robert E.
2201:10.1145/5684.5686
1777:Tarjan, Robert E.
1769:Sedgewick, Robert
1739:is not supported.
1700:
1585:. Here, it makes
1498:
1497:
711:time complexities
265:
2956:
2902:
2901:
2876:
2870:
2869:
2868:, pp. 52–58
2863:
2855:Brodal, Gerth S.
2851:
2845:
2844:
2824:
2814:
2796:
2790:
2789:
2779:
2759:
2743:
2737:
2736:
2727:(6): 1463–1485.
2718:
2705:
2699:
2698:
2678:
2668:
2657:
2651:
2650:
2630:
2618:
2612:
2611:
2609:
2595:
2589:
2588:
2567:
2561:
2560:
2559:
2539:
2530:
2529:
2527:
2526:
2512:
2506:
2505:
2503:
2502:
2496:
2490:. Archived from
2481:
2463:
2454:
2448:
2447:
2418:
2409:
2408:
2390:
2357:
2346:
2345:
2314:
2301:
2300:
2294:
2291:cite tech report
2286:
2284:
2273:
2267:
2266:
2239:
2219:
2213:
2212:
2194:
2174:
2168:
2167:
2135:
2129:
2128:
2119:
2102:
2097:
2082:
2076:
2075:
2048:
2039:
2030:
2021:
2020:
2018:
2017:
2011:
2005:. Archived from
1980:
1968:
1962:
1961:
1944:
1926:
1910:
1904:
1903:
1884:
1874:
1864:
1850:
1839:
1838:
1836:
1818:
1812:
1811:
1794:(1–4): 111–129.
1785:
1761:
1740:
1729:
1720:
1719:
1717:
1716:
1711:
1703:
1702:
1701:
1684:
1661:
1659:
1658:
1653:
1616:
1610:
1555:
1544:
1523:) time whenever
1506:
1398:Strict Fibonacci
1370:
1361:
1313:
1304:
1256:
1243:
1217:
1204:
1195:
1186:
1173:
1127:
1112:
1007:
902:
889:
876:
863:
850:
740:
716:
442:
440:
439:
434:
410:, which perform
402:
400:
399:
394:
361:
359:
358:
353:
316:
314:
313:
308:
281:
279:
278:
273:
268:
267:
266:
249:
214:
212:
211:
206:
165:
150:
131:
40:Robert Sedgewick
2964:
2963:
2959:
2958:
2957:
2955:
2954:
2953:
2934:
2933:
2910:
2905:
2898:
2878:
2877:
2873:
2861:
2853:
2852:
2848:
2841:
2822:10.1.1.233.1740
2812:
2798:
2797:
2793:
2777:10.1.1.309.8927
2757:
2745:
2744:
2740:
2716:
2707:
2706:
2702:
2695:
2666:
2659:
2658:
2654:
2628:
2620:
2619:
2615:
2607:
2597:
2596:
2592:
2585:
2569:
2568:
2564:
2541:
2540:
2533:
2524:
2522:
2514:
2513:
2509:
2500:
2498:
2494:
2479:10.1.1.353.7888
2461:
2456:
2455:
2451:
2444:
2420:
2419:
2412:
2397:10.1137/0215004
2359:
2358:
2349:
2342:
2316:
2315:
2304:
2287:
2282:
2275:
2274:
2270:
2256:
2221:
2220:
2216:
2192:10.1.1.117.9380
2176:
2175:
2171:
2156:10.1145/3147138
2137:
2136:
2132:
2117:10.1.1.502.6706
2100:
2088:
2084:
2083:
2079:
2065:
2046:
2037:
2032:
2031:
2024:
2015:
2013:
2009:
1978:
1970:
1969:
1965:
1942:10.1.1.106.2988
1924:
1914:Stasko, John T.
1912:
1911:
1907:
1901:
1882:10.1.1.748.7812
1862:
1852:
1851:
1842:
1834:
1820:
1819:
1815:
1783:
1763:
1762:
1753:
1749:
1744:
1743:
1730:
1723:
1675:
1664:
1663:
1662:upper bound of
1620:
1619:
1618:Lower bound of
1617:
1613:
1556:
1547:
1507:
1503:
707:
702:
673:
637:
613:
608:
581:
576:
563:
558:
517:
512:
487:
469:
457:Fibonacci heaps
416:
415:
408:Fibonacci heaps
364:
363:
323:
322:
284:
283:
240:
229:
228:
176:
175:
160:
145:
122:
60:Fibonacci heaps
56:tree structures
36:Michael Fredman
17:
12:
11:
5:
2962:
2960:
2952:
2951:
2946:
2936:
2935:
2932:
2931:
2922:
2909:
2908:External links
2906:
2904:
2903:
2896:
2871:
2846:
2839:
2791:
2770:(3): 596–615.
2738:
2700:
2693:
2676:10.1.1.549.471
2652:
2641:(4): 473–501.
2613:
2599:Takaoka, Tadao
2590:
2583:
2571:Okasaki, Chris
2562:
2550:(6): 839–857,
2531:
2507:
2449:
2442:
2422:Tarjan, Robert
2410:
2388:10.1.1.93.6678
2347:
2340:
2302:
2268:
2254:
2214:
2185:(4): 300–311.
2169:
2130:
2098:decrease cost"
2077:
2063:
2022:
1989:(4): 473–501.
1963:
1935:(3): 234–249,
1905:
1899:
1840:
1826:Sanders, Peter
1822:Mehlhorn, Kurt
1813:
1750:
1748:
1745:
1742:
1741:
1721:
1709:
1706:
1699:
1696:
1693:
1690:
1687:
1682:
1678:
1674:
1671:
1651:
1648:
1645:
1642:
1639:
1636:
1633:
1630:
1627:
1611:
1601:still runs in
1545:
1500:
1499:
1496:
1495:
1485:
1479:
1473:
1467:
1457:
1451:
1445:
1444:
1434:
1428:
1422:
1416:
1406:
1400:
1394:
1393:
1383:
1377:
1371:
1362:
1349:
1343:
1337:
1336:
1326:
1320:
1314:
1305:
1292:
1286:
1280:
1279:
1269:
1263:
1257:
1244:
1231:
1225:
1219:
1218:
1205:
1196:
1187:
1174:
1161:
1155:
1153:Bottom-up skew
1149:
1148:
1138:
1128:
1119:
1113:
1100:
1094:
1088:
1087:
1077:
1067:
1061:
1051:
1041:
1035:
1029:
1028:
1018:
1008:
999:
989:
979:
973:
967:
966:
956:
946:
936:
926:
916:
910:
904:
903:
890:
877:
864:
851:
838:
832:
826:
825:
815:
805:
795:
785:
775:
769:
763:
762:
759:
756:
753:
750:
747:
744:
735:Big O notation
706:
703:
677:
645:
618:
612:
609:
589:
580:
577:
567:
562:
559:
522:
516:
513:
511:
508:
478:
468:
465:
432:
429:
426:
423:
392:
389:
386:
383:
380:
377:
374:
371:
351:
348:
345:
342:
339:
336:
333:
330:
306:
303:
300:
297:
294:
291:
271:
264:
261:
258:
255:
252:
247:
243:
239:
236:
204:
201:
198:
195:
192:
189:
186:
183:
111:
110:
100:
90:
80:
74:
44:Daniel Sleator
28:data structure
15:
13:
10:
9:
6:
4:
3:
2:
2961:
2950:
2947:
2945:
2942:
2941:
2939:
2930:
2926:
2925:pairing heaps
2923:
2920:
2916:
2912:
2911:
2907:
2899:
2897:0-471-46983-1
2893:
2889:
2885:
2881:
2875:
2872:
2867:
2860:
2856:
2850:
2847:
2842:
2836:
2832:
2828:
2823:
2818:
2811:
2810:
2805:
2801:
2795:
2792:
2787:
2783:
2778:
2773:
2769:
2765:
2764:
2756:
2753:(July 1987).
2752:
2748:
2742:
2739:
2734:
2730:
2726:
2722:
2715:
2711:
2704:
2701:
2696:
2694:0-7695-2468-0
2690:
2686:
2682:
2677:
2672:
2665:
2664:
2656:
2653:
2648:
2644:
2640:
2636:
2635:
2627:
2624:(July 1999).
2623:
2617:
2614:
2606:
2605:
2600:
2594:
2591:
2586:
2584:9780521631242
2580:
2576:
2572:
2566:
2563:
2558:
2553:
2549:
2545:
2538:
2536:
2532:
2521:
2520:brilliant.org
2517:
2511:
2508:
2497:on 2016-02-05
2493:
2489:
2485:
2480:
2475:
2471:
2467:
2466:J. Algorithms
2460:
2453:
2450:
2445:
2439:
2435:
2431:
2427:
2423:
2417:
2415:
2411:
2406:
2402:
2398:
2394:
2389:
2384:
2380:
2376:
2375:
2370:
2366:
2362:
2356:
2354:
2352:
2348:
2343:
2341:0-262-03141-8
2337:
2333:
2332:
2327:
2323:
2319:
2313:
2311:
2309:
2307:
2303:
2298:
2292:
2281:
2280:
2272:
2269:
2265:
2261:
2257:
2251:
2247:
2243:
2238:
2233:
2229:
2225:
2218:
2215:
2210:
2206:
2202:
2198:
2193:
2188:
2184:
2180:
2173:
2170:
2165:
2161:
2157:
2153:
2149:
2145:
2141:
2134:
2131:
2127:
2123:
2118:
2113:
2109:
2108:
2099:
2095:
2091:
2081:
2078:
2074:
2070:
2066:
2064:0-7695-2468-0
2060:
2056:
2052:
2045:
2044:
2036:
2029:
2027:
2023:
2012:on 2011-07-21
2008:
2004:
2000:
1996:
1992:
1988:
1984:
1977:
1973:
1967:
1964:
1960:
1956:
1952:
1948:
1943:
1938:
1934:
1930:
1923:
1919:
1915:
1909:
1906:
1902:
1900:3-540-67690-2
1896:
1892:
1888:
1883:
1878:
1873:
1868:
1861:
1860:
1855:
1849:
1847:
1845:
1841:
1833:
1832:
1827:
1823:
1817:
1814:
1809:
1805:
1801:
1797:
1793:
1789:
1782:
1778:
1774:
1770:
1766:
1760:
1758:
1756:
1752:
1746:
1738:
1734:
1728:
1726:
1722:
1707:
1697:
1694:
1691:
1688:
1685:
1680:
1676:
1669:
1649:
1643:
1640:
1637:
1634:
1631:
1615:
1612:
1608:
1604:
1600:
1596:
1592:
1588:
1584:
1580:
1576:
1572:
1568:
1564:
1560:
1554:
1552:
1550:
1546:
1542:
1538:
1534:
1530:
1526:
1522:
1518:
1514:
1510:
1505:
1502:
1493:
1489:
1486:
1483:
1480:
1477:
1474:
1471:
1468:
1465:
1461:
1458:
1455:
1452:
1450:
1447:
1446:
1442:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1417:
1414:
1410:
1407:
1404:
1401:
1399:
1396:
1395:
1391:
1387:
1384:
1381:
1378:
1375:
1372:
1366:
1363:
1357:
1353:
1350:
1347:
1344:
1342:
1339:
1338:
1334:
1330:
1327:
1324:
1321:
1318:
1315:
1309:
1306:
1300:
1296:
1293:
1290:
1287:
1285:
1282:
1281:
1277:
1273:
1270:
1267:
1264:
1261:
1258:
1252:
1248:
1245:
1239:
1235:
1232:
1229:
1226:
1224:
1221:
1220:
1213:
1209:
1206:
1200:
1197:
1191:
1188:
1182:
1178:
1175:
1169:
1165:
1162:
1159:
1156:
1154:
1151:
1150:
1146:
1142:
1139:
1136:
1132:
1129:
1123:
1120:
1117:
1114:
1108:
1104:
1101:
1098:
1095:
1093:
1090:
1089:
1085:
1081:
1078:
1075:
1071:
1068:
1065:
1062:
1059:
1055:
1052:
1049:
1045:
1042:
1039:
1036:
1034:
1033:Skew binomial
1031:
1030:
1026:
1022:
1019:
1016:
1012:
1009:
1003:
1000:
997:
993:
990:
987:
983:
980:
977:
974:
972:
969:
968:
964:
960:
957:
954:
950:
947:
944:
940:
937:
934:
930:
927:
924:
920:
917:
914:
911:
909:
906:
905:
898:
894:
891:
885:
881:
878:
872:
868:
865:
859:
855:
852:
846:
842:
839:
836:
833:
831:
828:
827:
823:
819:
816:
813:
809:
806:
803:
799:
796:
793:
789:
786:
783:
779:
776:
773:
770:
768:
765:
764:
760:
757:
754:
752:decrease-key
751:
748:
745:
742:
741:
738:
736:
732:
728:
724:
720:
712:
704:
701:
697:
693:
689:
685:
681:
676:
671:
668:
664:
660:
656:
652:
648:
644:
642:
635:
632:
629:
625:
621:
617:
610:
606:
603:
600:
596:
592:
588:
586:
583:The function
578:
574:
570:
566:
560:
556:
553:
549:
545:
541:
537:
533:
529:
525:
521:
514:
509:
507:
504:
500:
496:
493:, supporting
492:
485:
481:
477:
475:
466:
464:
462:
458:
454:
450:
446:
427:
421:
413:
409:
404:
387:
384:
381:
378:
375:
346:
343:
340:
337:
334:
328:
320:
301:
298:
295:
289:
262:
259:
256:
253:
250:
245:
241:
234:
226:
222:
218:
199:
196:
193:
190:
187:
173:
169:
163:
157:
152:
148:
143:
139:
135:
129:
125:
120:
116:
108:
104:
101:
98:
94:
91:
88:
84:
81:
78:
75:
72:
69:
68:
67:
65:
61:
57:
53:
49:
48:Robert Tarjan
45:
41:
37:
33:
29:
26:
23:is a type of
22:
2929:Sartaj Sahni
2887:
2874:
2865:
2849:
2808:
2794:
2767:
2761:
2741:
2724:
2720:
2703:
2662:
2655:
2638:
2632:
2616:
2610:, p. 12
2603:
2593:
2574:
2565:
2547:
2543:
2523:. Retrieved
2519:
2510:
2499:. Retrieved
2492:the original
2469:
2465:
2452:
2425:
2381:(1): 52–69.
2378:
2372:
2330:
2278:
2271:
2227:
2217:
2182:
2178:
2172:
2147:
2143:
2133:
2104:
2093:
2089:
2080:
2042:
2014:. Retrieved
2007:the original
1986:
1982:
1966:
1932:
1928:
1908:
1858:
1854:Iacono, John
1830:
1816:
1791:
1788:Algorithmica
1787:
1737:decrease-key
1736:
1614:
1606:
1602:
1598:
1594:
1590:
1586:
1582:
1578:
1574:
1570:
1566:
1563:decrease-key
1562:
1540:
1536:
1532:
1528:
1524:
1520:
1516:
1512:
1508:
1504:
1491:
1487:
1481:
1475:
1469:
1463:
1459:
1453:
1440:
1436:
1430:
1424:
1418:
1412:
1408:
1402:
1389:
1385:
1379:
1373:
1364:
1355:
1351:
1345:
1332:
1328:
1322:
1316:
1307:
1298:
1294:
1288:
1284:Rank-pairing
1275:
1271:
1265:
1259:
1250:
1246:
1237:
1233:
1227:
1222:
1211:
1207:
1198:
1189:
1180:
1176:
1167:
1163:
1157:
1144:
1140:
1134:
1130:
1121:
1115:
1106:
1102:
1096:
1083:
1079:
1073:
1069:
1063:
1057:
1053:
1047:
1043:
1037:
1024:
1020:
1014:
1010:
1001:
995:
991:
985:
981:
975:
962:
958:
952:
948:
942:
938:
932:
928:
922:
918:
912:
896:
892:
883:
879:
870:
866:
857:
853:
844:
840:
834:
821:
817:
811:
807:
801:
797:
791:
787:
781:
777:
771:
730:
726:
722:
718:
708:
699:
695:
691:
687:
683:
679:
674:
669:
666:
662:
658:
654:
650:
646:
640:
638:
633:
630:
627:
623:
619:
614:
604:
601:
598:
594:
590:
584:
582:
572:
568:
564:
554:
551:
547:
543:
539:
535:
531:
527:
523:
518:
495:decrease-key
494:
491:RAM machines
488:
483:
479:
474:decrease-key
473:
472:support the
470:
461:decrease-key
460:
453:decrease-key
452:
449:decrease-key
448:
412:decrease-key
411:
405:
319:decrease-key
318:
225:decrease-key
224:
220:
216:
174:is at least
172:decrease-key
171:
161:
156:decrease-key
155:
153:
146:
141:
137:
133:
127:
123:
118:
112:
106:
102:
96:
93:decrease-key
92:
86:
82:
76:
70:
52:heap-ordered
21:pairing heap
20:
18:
2472:: 126–153.
2150:(4): 1–14.
1569:to that of
749:delete-min
641:merge-pairs
476:operation.
445:d-ary heaps
227:all run in
115:splay trees
2938:Categories
2525:2019-09-30
2501:2016-01-28
2016:2011-05-03
1747:References
1733:persistent
1605:(log
1599:delete-min
1597:is) while
1579:delete-min
1575:delete-min
1559:persistent
1531:(log
1462:(log
1411:(log
1354:(log
1297:(log
1249:(log
1236:(log
1179:(log
1166:(log
1133:(log
1105:(log
1072:(log
1056:(log
1046:(log
1013:(log
994:(log
984:(log
951:(log
941:(log
931:(log
921:(log
882:(log
869:(log
856:(log
843:(log
800:(log
790:(log
780:(log
761:make-heap
743:Operation
657:Empty
611:Delete-min
607:heap.elem
542:heap1
534:heap2
510:Operations
119:delete-min
103:delete-min
2817:CiteSeerX
2772:CiteSeerX
2671:CiteSeerX
2474:CiteSeerX
2405:0097-5397
2383:CiteSeerX
2237:1403.0252
2187:CiteSeerX
2112:CiteSeerX
2092:(log log
1937:CiteSeerX
1877:CiteSeerX
1872:1110.4428
1695:
1689:
1641:
1635:
1626:Ω
1509:make-heap
1341:Fibonacci
746:find-min
709:Here are
665:list
467:Structure
385:
379:
370:Θ
344:
338:
299:
260:
254:
197:
191:
182:Ω
54:multiway
32:amortized
2857:(1996),
2806:(2012).
2601:(1999),
2328:(1990).
2264:15216766
2209:43650389
2003:16115266
1974:(1999).
1959:17811811
1920:(1987),
1828:(2008).
1808:23664143
1779:(1986).
1527:runs in
1092:2–3 heap
971:Binomial
725:)" and "
700:H1234567
647:function
620:function
591:function
585:find-min
579:Find-min
569:function
524:function
321:runs in
134:find-min
71:find-min
2915:Haskell
2164:1182235
2073:2717102
1589:run in
1223:Pairing
908:Leftist
755:insert
733:)" see
168:Fredman
154:When a
144:run in
2894:
2837:
2819:
2774:
2691:
2673:
2581:
2476:
2440:
2403:
2385:
2338:
2262:
2252:
2207:
2189:
2162:
2114:
2071:
2061:
2001:
1957:
1939:
1897:
1879:
1806:
1595:insert
1571:insert
1449:Brodal
767:Binary
696:H34567
670:return
663:return
655:return
634:return
605:return
573:return
561:Insert
555:return
548:return
540:return
532:return
223:, and
217:insert
166:, but
151:time.
142:insert
140:, and
83:insert
46:, and
2862:(PDF)
2813:(PDF)
2758:(PDF)
2717:(PDF)
2667:(PDF)
2629:(PDF)
2608:(PDF)
2495:(PDF)
2462:(PDF)
2283:(PDF)
2260:S2CID
2232:arXiv
2205:S2CID
2160:S2CID
2101:(PDF)
2069:S2CID
2047:(PDF)
2038:(PDF)
2010:(PDF)
1999:S2CID
1979:(PDF)
1955:S2CID
1925:(PDF)
1867:arXiv
1863:(PDF)
1835:(PDF)
1804:S2CID
1784:(PDF)
758:meld
659:elsif
628:error
599:error
544:elsif
536:elsif
126:(log
107:melds
2892:ISBN
2835:ISBN
2689:ISBN
2579:ISBN
2438:ISBN
2401:ISSN
2336:ISBN
2297:link
2250:ISBN
2059:ISBN
1895:ISBN
1587:meld
1583:meld
1581:and
1567:meld
1557:For
1525:meld
1484:(1)
1478:(1)
1472:(1)
1456:(1)
1433:(1)
1427:(1)
1421:(1)
1405:(1)
1382:(1)
1376:(1)
1367:(1)
1348:(1)
1325:(1)
1319:(1)
1310:(1)
1291:(1)
1268:(1)
1262:(1)
1230:(1)
1201:(1)
1192:(1)
1160:(1)
1124:(1)
1118:(1)
1099:(1)
1066:(1)
1040:(1)
1004:(1)
978:(1)
915:(1)
837:(1)
830:Skew
774:(1)
692:H567
667:else
631:else
602:else
552:else
515:Meld
484:type
480:type
221:meld
138:meld
97:meld
87:meld
77:meld
25:heap
2917:in
2827:doi
2782:doi
2729:doi
2681:doi
2643:doi
2552:doi
2484:doi
2430:doi
2393:doi
2242:doi
2197:doi
2152:doi
2122:doi
2051:doi
1991:doi
1947:doi
1887:doi
1796:doi
1692:log
1686:log
1638:log
1632:log
1369:am.
1360:am.
1312:am.
1303:am.
1255:am.
1242:am.
1216:am.
1203:am.
1194:am.
1185:am.
1172:am.
1126:am.
1111:am.
1006:am.
901:am.
888:am.
875:am.
862:am.
849:am.
715:am.
688:H56
684:H34
680:H12
414:in
382:log
376:log
341:log
335:log
296:log
257:log
251:log
194:log
188:log
164:(1)
149:(1)
121:is
2940::
2927:,
2882:;
2864:,
2833:.
2825:.
2780:.
2768:34
2766:.
2760:.
2749:;
2725:40
2723:.
2719:.
2687:.
2679:.
2639:46
2637:.
2631:.
2546:,
2534:^
2518:.
2482:.
2470:12
2468:.
2464:.
2436:.
2413:^
2399:.
2391:.
2379:15
2377:.
2371:.
2363:;
2350:^
2324:;
2320:;
2305:^
2293:}}
2289:{{
2258:,
2248:,
2240:,
2203:.
2195:.
2183:29
2181:.
2158:.
2148:13
2146:.
2142:.
2120:,
2103:,
2067:,
2057:,
2040:,
2025:^
1997:.
1987:46
1985:.
1981:.
1953:,
1945:,
1933:30
1931:,
1927:,
1916:;
1893:,
1885:,
1875:,
1843:^
1824:;
1802:.
1790:.
1786:.
1775:;
1771:;
1767:;
1754:^
1724:^
1548:^
1494:)
1466:)
1443:)
1415:)
1392:)
1358:)
1335:)
1301:)
1278:)
1253:)
1240:)
1214:)
1183:)
1170:)
1147:)
1137:)
1109:)
1086:)
1076:)
1060:)
1050:)
1027:)
1017:)
998:)
988:)
965:)
955:)
945:)
935:)
925:)
899:)
886:)
873:)
860:)
847:)
824:)
814:)
804:)
794:)
784:)
651:if
643::
624:if
595:if
528:if
219:,
136:,
42:,
38:,
19:A
2900:.
2843:.
2829::
2788:.
2784::
2735:.
2731::
2697:.
2683::
2649:.
2645::
2587:.
2554::
2548:6
2528:.
2504:.
2486::
2446:.
2432::
2407:.
2395::
2344:.
2299:)
2244::
2234::
2211:.
2199::
2166:.
2154::
2124::
2096:)
2094:n
2090:O
2053::
2019:.
1993::
1949::
1889::
1869::
1810:.
1798::
1792:1
1708:.
1705:)
1698:n
1681:2
1677:2
1673:(
1670:O
1650:,
1647:)
1644:n
1629:(
1607:n
1603:O
1591:Θ
1541:n
1539:(
1537:Θ
1533:n
1529:O
1521:n
1519:(
1517:Θ
1513:n
1492:n
1490:(
1488:Θ
1482:Θ
1476:Θ
1470:Θ
1464:n
1460:Θ
1454:Θ
1441:n
1439:(
1437:Θ
1431:Θ
1425:Θ
1419:Θ
1413:n
1409:Θ
1403:Θ
1390:n
1388:(
1386:Θ
1380:Θ
1374:Θ
1365:Θ
1356:n
1352:O
1346:Θ
1333:n
1331:(
1329:Θ
1323:Θ
1317:Θ
1308:Θ
1299:n
1295:O
1289:Θ
1276:n
1274:(
1272:Θ
1266:Θ
1260:Θ
1251:n
1247:o
1238:n
1234:O
1228:Θ
1212:n
1210:(
1208:Θ
1199:Θ
1190:Θ
1181:n
1177:O
1168:n
1164:O
1158:Θ
1145:n
1143:(
1141:Θ
1135:n
1131:O
1122:Θ
1116:Θ
1107:n
1103:O
1097:Θ
1084:n
1082:(
1080:Θ
1074:n
1070:Θ
1064:Θ
1058:n
1054:Θ
1048:n
1044:Θ
1038:Θ
1025:n
1023:(
1021:Θ
1015:n
1011:Θ
1002:Θ
996:n
992:Θ
986:n
982:Θ
976:Θ
963:n
961:(
959:Θ
953:n
949:Θ
943:n
939:Θ
933:n
929:Θ
923:n
919:Θ
913:Θ
897:n
895:(
893:Θ
884:n
880:O
871:n
867:O
858:n
854:O
845:n
841:O
835:Θ
822:n
820:(
818:Θ
812:n
810:(
808:Θ
802:n
798:Θ
792:n
788:Θ
782:n
778:Θ
772:Θ
731:f
729:(
727:Θ
723:f
721:(
719:O
431:)
428:1
425:(
422:O
391:)
388:n
373:(
350:)
347:n
332:(
329:O
305:)
302:n
293:(
290:o
270:)
263:n
246:2
242:2
238:(
235:O
203:)
200:n
185:(
162:O
147:O
130:)
128:n
124:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.