Heap sort gradi binarno kopico iz polja, nato pa večkrat ekstrahira maksimum, da proizvede sortirano zaporedje. Teče v O(n log n) in je na mestu.
Max-kopica drži največji element v korenu. Zgradite kopico (O(n)), nato zamenjajte koren na konec, zmanjšajte kopico in ponovno heapificirajte (sift down) — n-krat.
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 naredi na mestu z sifting down znotraj polja.
Uporabite, ko potrebujete garantirano O(n log n) in O(1) dodatni pomnilnik (merge sort potrebuje O(n); quicksort tvega O(n²)). Ni stabilna in ima slabo lokalnost predpomnilnika, zato je v praksi pogosto počasnejša od quicksorta. Ista kopica poganja prioritetne vrste in iskanje top-k elementov.
Heap sort je edina pogosta vrsta sortiranja, ki je hkrati v najslabšem primeru O(n log n) in na mestu, kar ga naredi dragoceno v nastavitvah s omejenimi pomnilniki ali garantiranimi mejami.
Struktura kopice je osnovna — prioritetne vrste, Dijkstrin algoritem in streaming top-k.
Utrjuje idejo, da prava podatkovna struktura naredi algoritem učinkovit.
Knjižnica IT vprašanj za razgovore s podrobnimi odgovori — od začetnika do izkušenega.
Doniraj