Šakos rūšiavimas iš masyvo sukuria dvejetainę šaką, o tada pakartotinai išimami didžiausi elementai, kad būtų gauta surūšiuota tvarka. Jis vykdomas O(n log n) laiku ir yra in-place.
Max-šaka laiko didžiausią elementą šaknies vietoje. Sukurkite šaką (O(n)), tada sukeiskite šaknį galu, sumažinkite šaką ir vėl nuheapify (sift down) — n kartų.
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]
Klasikinis įgyvendinimas tai atlieka in-place, atliekant sift down masyve.
Naudokite, kai reikia garantuoto O(n log n) ir O(1) papildomos atminties (merge sort reikalinga O(n); quicksort rizikuoja O(n²)). Tai nėra stabilu ir turi prastą cache lokalybę, todėl praktikoje dažnai buvimas lėtesnis nei quicksort. Tą pačią šaką valdo priority queue ir topinimo k elementų paieška.
Šakos rūšiavimas yra vienintelis bendras rūšiavimas, kuris yra ir worst-case O(n log n), ir in-place, dėl kurio jis brangus atminčiu apribotuose arba garantuoto susijungimo nustatymuose.
Po to esanti šakos struktūra plačiai naudinga — priority queue, Dijkstros algoritmas ir streaming top-k.
Tai sustiprina idėją, kad teisinga duomenų struktūra algoritmo efektyvumą.
IT pokalbių klausimų biblioteka su išsamiais atsakymais — nuo Junior iki Senior.
Paaukoti