Kuhjasort (heapsort)

Mida programm teeb

Kuhjasort ehitab massiivist maksimaalse kuhja (iga vanem on suurem kui lapsed) ja võtab siis kordamööda suurima elemendi kuhja tipust viimasele kohale. Kuhi on binaarpuu, mis hoitakse massiivis: elemendi i lapsed on 2i + 1 ja 2i + 2. Filmil on nii massiiv kui puu. Algoritm vajab alati umbes n log n sammu ja ei kasuta lisamälu.