Heap sort ndërton një grumbull binar nga vargu, më pas nxjerr në mënyrë të përsëritur maksimimin për të prodhuar rendin e renditur. Ekzekutohet në O(n log n) dhe është në vend.
Një max-grumbull mban elementin më të madh në rrënjë. Ndërtojeni grumbullin (O(n)), më pas ndërroni rrënjën në fund, zvogëlojeni grumbullin dhe ri-heapifoni (sift down) — n herë.
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]
Një implementim klasik e bën këtë në vend duke bërë sift down brenda vargut.
Përdoreni kur keni nevojë për O(n log n) të garantuar dhe O(1) memorje shtesë (merge sort kërkon O(n); quicksort rrezikon O(n²)). Nuk është stabile dhe ka lokalitet të dobë cache-a, kështu që është shpesh më e ngadaltë në praktikë se quicksort. I njëjti grumbull fuqizon radhët prioritare dhe gjetjen e elementeve top-k.
Heap sort është e vetmja përkatëse renditje që është si në rastin më të keq O(n log n) ashtu edhe në vend, duke e bërë atë të çmueshme në mjediset e kufizuara me memorie ose të garantuara.
Struktura e grumbullit është gjerësisht e dobishme — radhët prioritare, algoritmi i Dijkstra, dhe streaming top-k.
Nè pengëson idenë se struktura e duhur e të dhënave e bën një algoritëm efikas.