Heap sort membangun binary heap dari array, kemudian secara berulang mengekstrak maksimum untuk menghasilkan urutan terurut. Berjalan dalam O(n log n) dan in-place.
Max-heap menyimpan elemen terbesar di akar. Bangun heap (O(n)), kemudian tukar akar ke akhir, kurangi heap, dan terapkan ulang sift down — n kali.
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]
Implementasi klasik melakukannya secara in-place dengan sift down dalam array.
Gunakan ketika Anda memerlukan O(n log n) terjamin dan O(1) memori tambahan (merge sort membutuhkan O(n); quicksort berisiko O(n²)). Hal ini tidak stabil dan memiliki lokalitas cache yang buruk, sehingga sering lebih lambat dalam praktik daripada quicksort. Struktur heap yang sama memberdayakan antrian prioritas dan menemukan elemen top-k.
Heap sort adalah satu-satunya pengurutan umum yang keduanya worst-case O(n log n) dan in-place, menjadikannya berharga dalam pengaturan terbatas memori atau batas terjamin.
Struktur heap yang mendasari sangat berguna — antrian prioritas, algoritma Dijkstra, dan top-k streaming.
Ini memperkuat gagasan bahwa struktur data yang tepat membuat algoritma efisien.
Perpustakaan pertanyaan wawancara IT dengan jawaban mendetail — dari Junior hingga Senior.
Donasi