Bagaimana cara kerja heap sort?

Question

Accepted Answer

**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**.

## Idenya

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.

## Contoh

```python
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.

## Kompleksitas

- **Waktu:** O(n log n) dalam semua kasus. **Ruang:** O(1) in-place.

## Kapan digunakan / jebakan

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.

## Mengapa ini penting

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.