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.
Ideja
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.
Primer
heapq
():
heapq.heapify(arr)
[heapq.heappop(arr)
_ ((arr))]
heap_sort([, , , , ])
