553:" variant. This is done by "merging up": after swapping the root with the last element of the heap, find the last (height 1) child of the root. Merge this with the root (its distinguished ancestor), resulting in a valid height-2 heap at the global root. Then go to the previous sibling (binary parent) of the last merged node, and merge again. Repeat until the root is reached, when it will be correct for the complete tree.
366:
ancestor is the same as its binary parent's. In the implicit tree, finding the binary parent is easy, but its reverse bit must be consulted to determine which type of child the node is. (Early papers used the term "grandparent" for the distinguished ancestor, a meaning confusingly different from the usual "parent of parent".)
467:
By swapping the binary children, the appropriate subset of the demoted ancestor's old children (which are safely less than or equal to it) are demoted with it. The demoted ancestor's new siblings are the first root's old children, promoted, which are safely less than or equal to the promoted first
365:
A node's parent in the multi-way tree is called its "distinguished ancestor". To find this in the binary tree, find the node's binary parent. If the node is the right child (first child), the parent is the distinguished ancestor. If the node is the left child (next sibling), its distinguished
423:. This requires exactly one comparison, between the roots. Whichever root is greater (assuming a max-heap) is the final root. Its first child is the losing root, which retains its children (right subtree). The winning root's children are installed as siblings of the losing root.
571:
Sifting up is done using the same process as in binary heaps. The new node is added at the leaf level, then compared with its distinguished ancestor and swapped if necessary (the merge operation). This is repeated until no more swaps are necessary or the root is reached.
1033:
We provide a catalogue of algorithms that optimize the standard algorithms in various ways. As the optimization criteria, we consider the worst-case running time, the number of instructions, branch mispredictions, cache misses, element comparisons, and element
459:
The second case works because, in the multi-way tree, each node keeps its children with it. The first root is promoted up the tree because it is greater than its distinguished ancestor. Thus, it is safely greater than all of the ancestor's previous children.
455:(The first root is greater.) The first root's binary children (first child and next sibling) are exchanged (using the reverse bit), and then the first root and its distinguished ancestor are exchanged (by copying).
463:
The previous ancestor, however, is not a safe parent for the first root's old children, because it is less than the first root and so it's not guaranteed to be greater than or equal to all of its children.
505:
the distinguished ancestor is simplified because the reverse bits in all parents of the heaps being merged are unmodified from their initial state ("not reversed"), and so do not need to be consulted.
193:) representation, this requires one "reverse bit" per internal node to indicate which child is considered the left child. A weak heap is thus not a strictly implicit data structure since it requires
426:
This operation can be performed on the implicit tree structure because the heaps being merged are never arbitrary. Rather, the two heaps are formed as part of sifting a node up the multi-way tree:
501:
merges. It can be done on various orders, but a simple bottom-up implementation works from the end of the array to the beginning, merging each node with its distinguished ancestor. Note that
561:
In a weak max-heap, the maximum value can be found (in constant time) as the value associated with the root node; similarly, in a weak min-heap, the minimum value can be found at the root.
487:. First, a weak heap is built out of all of the elements of the array, and then the root is repeatedly exchanged with the last element, which is sifted down to its proper place.
512:, performance is improved if subtrees are merged as soon as two of the same size become available, rather than merging all subtrees on one level before proceeding to the next.
804:
313:
node in a weak heap can be considered the root of a smaller weak heap by ignoring its next sibling. Nodes with no first child are automatically valid weak heaps.
297:
Viewed as a multi-way tree, each node in a weak heap is linked to two others: a "next sibling" and a "first child". In the implicit tree, the links are fixed, so
916:
433:
The second is the imaginary heap formed by linking the first root's distinguished ancestor (multi-way parent) to the first root's following siblings.
1333:
986:
937:
897:
874:
857:
1540:
76:
915:
Bruun, Asger; Edelkamp, Stefan; Katajainen, Jyrki; Rasmussen, Jens (2010). "Policy-Based
Benchmarking of Weak Heaps and Their Relatives".
96:
For every node, the value associated with that node is greater than or equal to the values associated with all nodes in its right subtree.
452:(The distinguished ancestor is greater or equal.) Nothing needs to be moved, and the result of the merge is the distinguished ancestor.
1084:
1608:
2072:
178:
elements is exactly isomorphic to a binomial heap of the same size, but the two algorithms handle sizes which are not a power of
1200:
1631:
75:
stored as a binary tree using the "right-child left-sibling" convention. (This is equivalent to, but reversed from, the usual
1939:
186:
185:
Weak heaps require the ability to exchange the left and right children (and associated subtrees) of a node. In an explicit (
1972:
60:
471:
After this operation, it is uncertain whether the invariant is maintained between the new distinguished ancestor and
220:
bit per node). However, it is often possible to find space for this extra bit within the node structure, such as by
1165:
2077:
1646:
1550:
951:
1944:
1106:
41:
1852:
1732:
1686:
1077:
835:
777:
685:
182:
differently: a binomial heap uses multiple perfect trees, while a weak heap uses a single imperfect tree.
2013:
1601:
1244:
1093:
625:
comparisons. They were later investigated as a more generally applicable priority queue data structure.
59:, so is particularly useful when comparison is expensive, such as when comparing strings using the full
826:
1992:
1857:
1712:
1234:
1189:
190:
690:
2008:
1747:
1348:
1124:
840:
782:
1204:
903:
412:
Like binomial heaps, the fundamental operation on weak heaps is merging two heaps of equal height
409:.) Thus, even a simple iterative algorithm for finding the distinguished ancestor is sufficient.
1898:
1873:
1847:
1651:
1515:
1474:
1300:
1290:
1169:
943:
795:
743:
1717:
568:
data structure: insert, delete-min, delete, or decrease-key, in logarithmic time per operation.
345:. These may be found by following the first child link and then successive next sibling links.
981:, vol. 128, Darlinghurst, Australia: Australian Computer Society, Inc., pp. 103–112,
82:
In the multi-way tree, and assuming a max-heap, each parent's key is greater than or equal to (
51:
using weak heaps, weak-heapsort, uses a number of comparisons that is close to the theoretical
1656:
1617:
1409:
1110:
1070:
982:
933:
893:
853:
48:
1959:
1826:
1594:
1500:
1051:
1022:
925:
885:
845:
787:
735:
695:
17:
707:
301:
of the two links is the sibling and which the first child is indicated by the reverse bit.
2020:
1903:
1775:
1676:
1671:
1661:
1444:
1194:
703:
56:
1681:
884:. Lecture Notes in Computer Science. Vol. 6049. Springer-Verlag. pp. 424–435.
834:, Lecture Notes in Computer Science, vol. 1770, Springer-Verlag, pp. 254–266,
599:
algorithm that (unlike the standard heap sort using binary heaps) could be used to sort
2025:
1934:
1801:
1770:
1755:
1636:
1397:
1392:
1275:
1209:
670:
580:
576:
565:
483:
Weak heaps may be used to sort an array, in essentially the same way as a conventional
221:
72:
29:
25:
979:
Proceedings of the
Eighteenth Computing: The Australasian Theory Symposium (CATS 2012)
2066:
1893:
1666:
1545:
1525:
1368:
1257:
1184:
1041:
44:
binary tree like a binary heap, and has the efficiency guarantees of binomial heaps.
37:
1119:
971:
882:
Proceedings of the 9th
International Symposium on Experimental Algorithms (SEA 2010)
799:
1908:
1821:
1691:
1505:
1469:
1285:
1280:
1262:
1174:
947:
818:
747:
643:
103:
The last condition is a consequence of the fact that an implicit binary tree is a
929:
889:
430:
The first is a normal weak heap (whose next sibling link exists, but is ignored).
152:
This structure is very similar to that of a binomial heap, with a tree of height
2041:
1883:
1707:
1641:
1555:
1520:
1510:
1424:
1358:
1353:
1343:
1252:
1101:
1055:
475:
distinguished ancestor, so the operation is repeated until the root is reached.
104:
52:
33:
1007:
1987:
1967:
1949:
1913:
1842:
1780:
1765:
1727:
1565:
1535:
1495:
1338:
1267:
1214:
1134:
1027:
762:
699:
189:-based) representation of the tree, this is straightforward. In an implicit (
115:
849:
1982:
1918:
1888:
1878:
1816:
1811:
1806:
1737:
1722:
1570:
1530:
1377:
1295:
1040:
Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki; Weiß, Armin (July 2013).
596:
509:
873:
Bruun, Asger; Edelkamp, Stefan; Katajainen, Jyrki; Rasmussen, Jens (2010).
86:) all the child keys (and thus, by induction, all members of the subtree).
1459:
1149:
791:
99:
The leaves of the tree have heights that are all within one of each other.
2051:
2046:
1760:
1575:
1449:
1429:
1402:
1387:
1139:
564:
As with binary heaps, weak heaps can support the typical operations of a
550:
484:
89:
Expressed as a binary tree, this translates to the following invariants:
642:
Edelkamp, Stefan (26 May 2011), Pieterse, Vreda; Black, Paul E. (eds.),
1977:
1560:
1464:
1439:
1382:
1229:
1159:
1154:
1129:
1062:
924:. Lecture Notes in Computer Science. Vol. 6049. pp. 424–435.
739:
448:
After comparing the two roots, the merge proceeds in one of two ways:
1586:
1479:
1454:
1434:
1419:
1328:
1219:
1144:
441:
possibly between the first root and its distinguished ancestor. All
1006:
Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (November 2013).
1323:
1224:
1179:
1047:
669:
Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (October 2012),
110:
The structure of this tree maps very neatly onto the traditional
1315:
141:. This root has no siblings, only a first child, which is node
1590:
1066:
508:
As with heapsort, if the array to be sorted is larger than the
445:
nodes are less than or equal to their distinguished ancestors.
972:"The Weak-heap Family of Priority Queues in Theory and Praxis"
875:"Policy-Based Benchmarking of Weak Heaps and Their Relatives"
1046:. Combinatorial Algorithms - 24th International Workshop.
970:
Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (2012),
671:"The weak-heap data structure: variants and applications"
71:
A weak heap is most easily understood as a heap-ordered
763:"Performance Engineering Case Study: Heap Construction"
761:
Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000).
437:
At the beginning, the heap invariants apply everywhere
579:
insertions and decrease-keys, matching the time for
2034:
2001:
1958:
1927:
1866:
1835:
1794:
1746:
1700:
1624:
1488:
1367:
1314:
1243:
1100:
575:Variants of the weak heap structure allow constant
174:. A perfect (no missing leaves) weak heap with
156:being composed of a root plus trees of heights
118:) implicit binary tree arrangement, where node
1602:
1078:
57:number of comparisons required to sort a list
8:
726:Dutton, Ronald D. (1993), "Weak-heap sort",
664:
662:
648:Dictionary of Algorithms and Data Structures
1043:Weak Heaps and Friends: Recent Developments
957:on 2016-12-27 – via Semantic Scholar.
515:Sifting down in a weak heap can be done in
369:Although the distinguished ancestor may be
1609:
1595:
1587:
1085:
1071:
1063:
721:
719:
717:
1026:
839:
781:
689:
129:and a first child (right child) numbered
122:has a next sibling (left child) numbered
770:ACM Journal of Experimental Algorithmics
341:, and so on to the last child of height
137:, by adding an additional root numbered
634:
592:
391:, and half of the time we recurse, so
40:. It can be stored in an array as an
7:
348:It also has next siblings of height
77:left-child right-sibling binary tree
1785:
327:children: a first child of height
227:In the implicit binary tree, node
14:
416:, to make a weak heap of height
1632:Computational complexity theory
821:(2000), "On the performance of
93:The root node has no left child
1015:Journal of Discrete Algorithms
678:Journal of Discrete Algorithms
591:Weak heaps were introduced by
1:
379:levels high in the tree, the
930:10.1007/978-3-642-13193-6_36
890:10.1007/978-3-642-13193-6_36
32:, combining features of the
1056:10.1007/978-3-642-45278-9_1
529:comparisons, as opposed to
334:, a second child of height
61:Unicode collation algorithm
2094:
1940:Batcher odd–even mergesort
494:elements can be formed in
224:which is already present.
1028:10.1016/j.jda.2013.07.002
700:10.1016/j.jda.2012.04.010
557:Priority queue operations
1945:Pairwise sorting network
1541:Left-child right-sibling
850:10.1007/3-540-46541-3_21
587:History and applications
305:Operations on weak heaps
2073:Heaps (data structures)
1973:Kirkpatrick–Reisch sort
1371:data partitioning trees
1329:C-trie (compressed ADT)
1008:"Weak heaps engineered"
918:Experimental Algorithms
595:, as part of a variant
1853:Oscillating merge sort
1733:Proportion extend sort
1687:Transdichotomous model
539:for a binary heap, or
2014:Pre-topological order
792:10.1145/351827.384257
1993:Merge-insertion sort
1858:Polyphase merge sort
1713:Cocktail shaker sort
1551:Log-structured merge
1094:Tree data structures
805:Alternate PDF source
105:complete binary tree
2009:Topological sorting
1771:Cartesian tree sort
1899:Interpolation sort
1874:American flag sort
1867:Distribution sorts
1848:Cascade merge sort
1618:Sorting algorithms
1516:Fractal tree index
1111:associative arrays
817:Edelkamp, Stefan;
740:10.1007/bf01990520
551:bottom-up heapsort
387:. (It's at least
280:, and right child
204:additional space (
2060:
2059:
2035:Impractical sorts
1584:
1583:
988:978-1-921770-09-8
939:978-3-642-13192-9
899:978-3-642-13192-9
859:978-3-540-67141-1
603:items using only
316:A node of height
231:with reverse bit
222:tagging a pointer
49:sorting algorithm
2085:
2078:Comparison sorts
1968:Block merge sort
1928:Concurrent sorts
1827:Patience sorting
1611:
1604:
1597:
1588:
1087:
1080:
1073:
1064:
1059:
1036:
1030:
1012:
993:
991:
976:
967:
961:
958:
956:
950:. Archived from
923:
910:
908:
902:. Archived from
879:
870:
864:
862:
843:
833:
814:
808:
803:
785:
767:
758:
752:
750:
723:
712:
710:
693:
675:
666:
657:
656:
655:
654:
639:
624:
602:
548:
538:
528:
500:
493:
422:
415:
408:
401:
390:
386:
378:
361:
354:
344:
340:
333:
326:
319:
293:
279:
265:
264:
261:
259:
258:
255:
252:
244:
239:
230:
219:
217:
216:
213:
210:
203:
181:
177:
173:
169:
162:
155:
148:
144:
140:
136:
128:
121:
113:
85:
18:computer science
2093:
2092:
2088:
2087:
2086:
2084:
2083:
2082:
2063:
2062:
2061:
2056:
2030:
2021:Pancake sorting
1997:
1954:
1923:
1904:Pigeonhole sort
1862:
1831:
1795:Insertion sorts
1790:
1776:Tournament sort
1748:Selection sorts
1742:
1696:
1677:Integer sorting
1672:Sorting network
1662:Comparison sort
1620:
1615:
1585:
1580:
1484:
1363:
1310:
1239:
1235:Weight-balanced
1190:Order statistic
1104:
1096:
1091:
1039:
1010:
1005:
1002:
1000:Further reading
997:
996:
989:
974:
969:
968:
964:
954:
940:
921:
914:
906:
900:
877:
872:
871:
867:
860:
831:
816:
815:
811:
765:
760:
759:
755:
725:
724:
715:
691:10.1.1.455.1213
673:
668:
667:
660:
652:
650:
641:
640:
636:
631:
611:
604:
600:
589:
581:Fibonacci heaps
559:
544:
540:
534:
530:
523:
516:
495:
491:
490:A weak heap of
481:
417:
413:
403:
402:, meaning that
392:
388:
384:
374:
370:
356:
349:
342:
335:
328:
321:
317:
307:
291:
281:
277:
267:
262:
256:
253:
248:
247:
245:
242:
241:
237:
232:
228:
214:
211:
208:
207:
205:
194:
179:
175:
171:
164:
157:
153:
146:
142:
138:
130:
123:
119:
111:
83:
69:
30:priority queues
12:
11:
5:
2091:
2089:
2081:
2080:
2075:
2065:
2064:
2058:
2057:
2055:
2054:
2049:
2044:
2038:
2036:
2032:
2031:
2029:
2028:
2026:Spaghetti sort
2023:
2018:
2017:
2016:
2005:
2003:
1999:
1998:
1996:
1995:
1990:
1985:
1980:
1975:
1970:
1964:
1962:
1956:
1955:
1953:
1952:
1947:
1942:
1937:
1935:Bitonic sorter
1931:
1929:
1925:
1924:
1922:
1921:
1916:
1911:
1906:
1901:
1896:
1891:
1886:
1881:
1876:
1870:
1868:
1864:
1863:
1861:
1860:
1855:
1850:
1845:
1839:
1837:
1833:
1832:
1830:
1829:
1824:
1819:
1814:
1809:
1804:
1802:Insertion sort
1798:
1796:
1792:
1791:
1789:
1788:
1786:Weak-heap sort
1783:
1778:
1773:
1768:
1763:
1758:
1756:Selection sort
1752:
1750:
1744:
1743:
1741:
1740:
1735:
1730:
1725:
1720:
1715:
1710:
1704:
1702:
1701:Exchange sorts
1698:
1697:
1695:
1694:
1689:
1684:
1679:
1674:
1669:
1664:
1659:
1654:
1649:
1644:
1639:
1637:Big O notation
1634:
1628:
1626:
1622:
1621:
1616:
1614:
1613:
1606:
1599:
1591:
1582:
1581:
1579:
1578:
1573:
1568:
1563:
1558:
1553:
1548:
1543:
1538:
1533:
1528:
1523:
1518:
1513:
1508:
1503:
1498:
1492:
1490:
1486:
1485:
1483:
1482:
1477:
1472:
1467:
1462:
1457:
1452:
1447:
1442:
1437:
1432:
1427:
1422:
1417:
1400:
1395:
1390:
1385:
1380:
1374:
1372:
1365:
1364:
1362:
1361:
1356:
1351:
1349:Ternary search
1346:
1341:
1336:
1331:
1326:
1320:
1318:
1312:
1311:
1309:
1308:
1303:
1298:
1293:
1288:
1283:
1278:
1273:
1265:
1260:
1255:
1249:
1247:
1241:
1240:
1238:
1237:
1232:
1227:
1222:
1217:
1212:
1207:
1197:
1192:
1187:
1182:
1177:
1172:
1162:
1157:
1152:
1147:
1142:
1137:
1132:
1127:
1122:
1116:
1114:
1098:
1097:
1092:
1090:
1089:
1082:
1075:
1067:
1061:
1060:
1037:
1001:
998:
995:
994:
987:
962:
960:
959:
938:
909:on 2017-08-11.
898:
865:
858:
841:10.1.1.21.1863
809:
783:10.1.1.35.3248
753:
734:(3): 372–381,
713:
658:
633:
632:
630:
627:
609:
588:
585:
577:amortized time
566:priority queue
558:
555:
542:
532:
521:
480:
479:Weak-heap sort
477:
457:
456:
453:
435:
434:
431:
372:
306:
303:
289:
275:
235:
101:
100:
97:
94:
73:multi-way tree
68:
65:
26:data structure
13:
10:
9:
6:
4:
3:
2:
2090:
2079:
2076:
2074:
2071:
2070:
2068:
2053:
2050:
2048:
2045:
2043:
2040:
2039:
2037:
2033:
2027:
2024:
2022:
2019:
2015:
2012:
2011:
2010:
2007:
2006:
2004:
2000:
1994:
1991:
1989:
1986:
1984:
1981:
1979:
1976:
1974:
1971:
1969:
1966:
1965:
1963:
1961:
1957:
1951:
1948:
1946:
1943:
1941:
1938:
1936:
1933:
1932:
1930:
1926:
1920:
1917:
1915:
1912:
1910:
1907:
1905:
1902:
1900:
1897:
1895:
1894:Counting sort
1892:
1890:
1887:
1885:
1882:
1880:
1877:
1875:
1872:
1871:
1869:
1865:
1859:
1856:
1854:
1851:
1849:
1846:
1844:
1841:
1840:
1838:
1834:
1828:
1825:
1823:
1820:
1818:
1815:
1813:
1810:
1808:
1805:
1803:
1800:
1799:
1797:
1793:
1787:
1784:
1782:
1779:
1777:
1774:
1772:
1769:
1767:
1764:
1762:
1759:
1757:
1754:
1753:
1751:
1749:
1745:
1739:
1736:
1734:
1731:
1729:
1726:
1724:
1721:
1719:
1718:Odd–even sort
1716:
1714:
1711:
1709:
1706:
1705:
1703:
1699:
1693:
1690:
1688:
1685:
1683:
1682:X + Y sorting
1680:
1678:
1675:
1673:
1670:
1668:
1667:Adaptive sort
1665:
1663:
1660:
1658:
1655:
1653:
1650:
1648:
1645:
1643:
1640:
1638:
1635:
1633:
1630:
1629:
1627:
1623:
1619:
1612:
1607:
1605:
1600:
1598:
1593:
1592:
1589:
1577:
1574:
1572:
1569:
1567:
1564:
1562:
1559:
1557:
1554:
1552:
1549:
1547:
1544:
1542:
1539:
1537:
1534:
1532:
1529:
1527:
1526:Hash calendar
1524:
1522:
1519:
1517:
1514:
1512:
1509:
1507:
1504:
1502:
1499:
1497:
1494:
1493:
1491:
1487:
1481:
1478:
1476:
1473:
1471:
1468:
1466:
1463:
1461:
1458:
1456:
1453:
1451:
1448:
1446:
1443:
1441:
1438:
1436:
1433:
1431:
1428:
1426:
1423:
1421:
1418:
1415:
1413:
1407:
1405:
1401:
1399:
1396:
1394:
1391:
1389:
1386:
1384:
1381:
1379:
1376:
1375:
1373:
1370:
1366:
1360:
1357:
1355:
1352:
1350:
1347:
1345:
1342:
1340:
1337:
1335:
1332:
1330:
1327:
1325:
1322:
1321:
1319:
1317:
1313:
1307:
1304:
1302:
1301:van Emde Boas
1299:
1297:
1294:
1292:
1291:Skew binomial
1289:
1287:
1284:
1282:
1279:
1277:
1274:
1272:
1270:
1266:
1264:
1261:
1259:
1256:
1254:
1251:
1250:
1248:
1246:
1242:
1236:
1233:
1231:
1228:
1226:
1223:
1221:
1218:
1216:
1213:
1211:
1208:
1206:
1202:
1198:
1196:
1193:
1191:
1188:
1186:
1183:
1181:
1178:
1176:
1173:
1171:
1170:Binary search
1167:
1163:
1161:
1158:
1156:
1153:
1151:
1148:
1146:
1143:
1141:
1138:
1136:
1133:
1131:
1128:
1126:
1123:
1121:
1118:
1117:
1115:
1112:
1108:
1103:
1099:
1095:
1088:
1083:
1081:
1076:
1074:
1069:
1068:
1065:
1057:
1053:
1049:
1045:
1044:
1038:
1035:
1029:
1024:
1020:
1016:
1009:
1004:
1003:
999:
990:
984:
980:
973:
966:
963:
953:
949:
945:
941:
935:
931:
927:
920:
919:
913:
912:
905:
901:
895:
891:
887:
883:
876:
869:
866:
861:
855:
851:
847:
842:
837:
830:
829:
824:
823:WEAK-HEAPSORT
820:
819:Wegener, Ingo
813:
810:
806:
801:
797:
793:
789:
784:
779:
775:
771:
764:
757:
754:
749:
745:
741:
737:
733:
729:
722:
720:
718:
714:
709:
705:
701:
697:
692:
687:
683:
679:
672:
665:
663:
659:
649:
645:
638:
635:
628:
626:
622:
618:
615: +
614:
607:
598:
594:
593:Dutton (1993)
586:
584:
582:
578:
573:
569:
567:
562:
556:
554:
552:
547:
541:1.5 log
537:
526:
519:
513:
511:
506:
504:
498:
488:
486:
478:
476:
474:
469:
465:
461:
454:
451:
450:
449:
446:
444:
440:
432:
429:
428:
427:
424:
420:
410:
406:
399:
395:
382:
377:
367:
363:
359:
352:
346:
338:
331:
324:
314:
312:
304:
302:
300:
295:
292:
285:
278:
271:
266:, left child
251:
238:
225:
223:
201:
197:
192:
188:
183:
167:
160:
150:
134:
127:
117:
108:
106:
98:
95:
92:
91:
90:
87:
80:
78:
74:
66:
64:
62:
58:
54:
50:
45:
43:
39:
38:binomial heap
35:
31:
27:
23:
19:
1960:Hybrid sorts
1909:Proxmap sort
1822:Library sort
1692:Quantum sort
1411:
1403:
1305:
1268:
1201:Left-leaning
1107:dynamic sets
1102:Search trees
1042:
1032:
1018:
1014:
978:
965:
952:the original
917:
904:the original
881:
868:
827:
822:
812:
773:
769:
766:(PostScript)
756:
731:
727:
681:
677:
651:, retrieved
647:
637:
620:
616:
612:
605:
590:
574:
570:
563:
560:
545:
535:
524:
517:
514:
507:
502:
496:
489:
482:
472:
470:
466:
462:
458:
447:
442:
438:
436:
425:
418:
411:
404:
397:
393:
383:distance is
380:
375:
368:
364:
357:
350:
347:
336:
329:
322:
315:
310:
308:
298:
296:
287:
283:
273:
269:
249:
233:
226:
199:
195:
184:
165:
158:
151:
132:
125:
109:
102:
88:
81:
70:
46:
21:
15:
2042:Stooge sort
1884:Bucket sort
1836:Merge sorts
1708:Bubble sort
1652:Inplacement
1642:Total order
1501:Exponential
1489:Other trees
684:: 187–205,
644:"weak-heap"
531:2 log
240:has parent
67:Description
53:lower bound
34:binary heap
2067:Categories
1988:Spreadsort
1950:Samplesort
1914:Radix sort
1843:Merge sort
1781:Cycle sort
1766:Smoothsort
1728:Gnome sort
1445:Priority R
1195:Palindrome
1050:, France.
828:Stacs 2000
653:2015-12-01
629:References
309:Note that
116:Ahnentafel
1983:Introsort
1919:Flashsort
1889:Burstsort
1879:Bead sort
1817:Tree sort
1812:Splaysort
1807:Shellsort
1738:Quicksort
1723:Comb sort
1657:Stability
1531:iDistance
1410:implicit
1398:Hilbert R
1393:Cartesian
1276:Fibonacci
1210:Scapegoat
1205:Red–black
1021:: 83–97.
836:CiteSeerX
778:CiteSeerX
686:CiteSeerX
608: log
597:heap sort
549:for the "
510:CPU cache
22:weak heap
2052:Bogosort
2047:Slowsort
1761:Heapsort
1546:Link/cut
1258:Binomial
1185:Interval
800:16705375
485:heapsort
114:-based (
42:implicit
1978:Timsort
1506:Fenwick
1470:Segment
1369:Spatial
1286:Pairing
1281:Leftist
1203:)
1175:Dancing
1168:)
1166:Optimal
948:1334592
748:5387832
708:2960353
503:finding
381:average
362:, etc.
260:
246:
218:
206:
187:pointer
170:, ...,
147:2×0 + 1
55:on the
1625:Theory
1556:Merkle
1521:Fusion
1511:Finger
1435:Octree
1425:Metric
1359:Y-fast
1354:X-fast
1344:Suffix
1263:Brodal
1253:Binary
1034:moves.
985:
946:
936:
896:
856:
838:
798:
780:
776:(15).
746:
706:
688:
520:= ⌈log
468:root.
439:except
396:= 1 +
286:+ 1 −
2002:Other
1647:Lists
1566:Range
1536:K-ary
1496:Cover
1339:Radix
1324:Ctrie
1316:Tries
1245:Heaps
1225:Treap
1215:Splay
1180:HTree
1135:(a,b)
1125:2–3–4
1048:Rouen
1011:(PDF)
975:(PDF)
955:(PDF)
944:S2CID
922:(PDF)
907:(PDF)
878:(PDF)
832:(PDF)
796:S2CID
744:S2CID
674:(PDF)
443:other
311:every
299:which
191:array
24:is a
1571:SPQR
1450:Quad
1378:Ball
1334:Hash
1306:Weak
1296:Skew
1271:-ary
983:ISBN
934:ISBN
894:ISBN
854:ISBN
320:has
36:and
28:for
20:, a
1576:Top
1430:MVP
1388:BSP
1140:AVL
1120:2–3
1052:doi
1023:doi
926:doi
886:doi
846:doi
825:",
788:doi
736:doi
728:BIT
696:doi
499:− 1
473:its
407:= 2
371:log
360:− 2
353:− 1
339:− 2
332:− 1
325:− 1
168:− 2
161:− 1
149:).
135:+ 1
79:.)
16:In
2069::
1561:PQ
1475:VP
1465:R*
1460:R+
1440:PH
1414:-d
1406:-d
1383:BK
1230:UB
1155:B*
1150:B+
1130:AA
1031:.
1019:23
1017:.
1013:.
977:,
942:.
932:.
911:.
892:.
880:.
852:,
844:,
794:.
786:.
772:.
768:.
742:,
732:33
730:,
716:^
704:MR
702:,
694:,
682:16
680:,
676:,
661:^
646:,
583:.
421:+1
400:/2
355:,
294:.
272:+
163:,
107:.
63:.
47:A
1610:e
1603:t
1596:v
1480:X
1455:R
1420:M
1416:)
1412:k
1408:(
1404:k
1269:d
1220:T
1199:(
1164:(
1160:B
1145:B
1113:)
1109:/
1105:(
1086:e
1079:t
1072:v
1058:.
1054::
1025::
992:.
928::
888::
863:.
848::
807:.
802:.
790::
774:5
751:.
738::
711:.
698::
623:)
621:n
619:(
617:O
613:n
610:2
606:n
601:n
546:n
543:2
536:n
533:2
527:⌉
525:n
522:2
518:h
497:n
492:n
419:h
414:h
405:D
398:D
394:D
389:1
385:2
376:n
373:2
358:h
351:h
343:1
337:h
330:h
323:h
318:h
290:k
288:r
284:k
282:2
276:k
274:r
270:k
268:2
263:⌋
257:2
254:/
250:k
243:⌊
236:k
234:r
229:k
215:2
212:/
209:1
202:)
200:n
198:(
196:O
180:2
176:2
172:1
166:h
159:h
154:h
145:(
143:1
139:0
133:k
131:2
126:k
124:2
120:k
112:1
84:≥
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.