Sortiranje hrpom gradi binarnu hrpu iz niza, zatim ponavlja vađenje maksimuma da bi se dobio sortiran redoslijed. Radi se u O(n log n) i je na mjestu.
Ideja
Max-hrpa čuva najveći element u koriznu. Izgradi hrpu (O(n)), zatim zamijeni korijen na kraju, skupi hrpu i ponovno primijeni svojstvo hrpe (sift down) — n puta.
Primjer
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]
Klasična implementacija to radi na mjestu primjenom sift down unutar niza.
Složenost
- Vrijeme: O(n log n) u svim slučajevima. Prostor: O(1) na mjestu.
Kada koristiti / zamke
Koristite kada trebate garantirane O(n log n) i O(1) dodatnu memoriju (merge sort trebata O(n); quicksort risira O(n²)). Nije stabilna i ima lošu lokalnost cache memorije, tako da je u praksi često sporija od quicksorta. Ista struktura hrpe osnažuje redove prioriteta i pronalaženje top-k elemenata.
Zašto je važna
Sortiranje hrpom je jedina česta vrsta sortiranja koja je i O(n log n) u najgorem slučaju i na mjestu, što je čini vrijednom u memorijski ograničenim ili garantirano ograničenim okruženjima.
Temeljna struktura hrpe je značajno korisna — redovi prioriteta, Dijkstrin algoritam i streamanje top-k.
To učvršćuje ideju da prava struktura podataka čini algoritam učinkovitim.