A kupacrendezés egy bináris kupacot épít az tömbből, majd többször kivonja a maximumot a rendezett sorrend eléréséhez. O(n log n) időben fut és helyben működik.
Egy max-kupac a gyökérnél tartja a legnagyobb elemet. Építs kupacot (O(n)), majd cseréld ki a gyökeret a végén, csökkentsd a kupacot, és alkalmázd újra a kupac-tulajdonságot (sift down) — n alkalommal.
import heapq
def heap_sort(arr):
heapq.heapify(arr) # min-heap in O(n)
return [heapq.heappop(arr) # pop smallest n times
for _ in range(len(arr))]
heap_sort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
Egy klasszikus megvalósítás helyben végzi a sift down alkalmazást a tömbön belül.
Használd, amikor garantált O(n log n) és O(1) extra memória szükséges (merge sort O(n)-et igényel; quicksort O(n²) kockázat). Nem stabil és gyenge cache lokalitása van, így a gyakorlatban gyakran lassabb a quicksortnál. Ugyanez a kupacstruktúra hajtja a prioritási sorokat és a top-k elemek keresését.
A kupacrendezés az egyetlen közönséges rendezési algoritmus, amely egyszerre O(n log n) a legrosszabb esetben és helyben működik, ezáltal értékessé téve a memória-korlátozott vagy garantált-határolt beállításokban.
A mögöttes kupacstruktúra széles körben hasznos — prioritási sorok, Dijkstra algoritmusa és streamelt top-k.
Megerősíti azt az ideát, hogy a helyes adatstruktúra hatékonnyá tesz egy algoritmust.