Bagaimana cara heap sort berfungsi?

Question

Accepted Answer

**Heap sort** membina **binary heap** daripada array, kemudian secara berulang mengekstrak maksimum untuk menghasilkan susunan yang disusun. Ia berjalan dalam **O(n log n)** dan **in-place**.

## Idea

Max-heap menyimpan elemen terbesar di akar. Bina heap (O(n)), kemudian tukarkan akar ke hujung, susutkan heap, dan padu-semulakan (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 in-place dengan sift down dalam array.

## Kerumitan

- **Masa:** O(n log n) dalam semua kes. **Ruang:** O(1) in-place.

## Bila hendak digunakan / jebakan

Gunakan apabila anda memerlukan **O(n log n) terjamin** *dan* **memori tambahan O(1)** (merge sort memerlukan O(n); quicksort berisiko O(n²)). Ia **tidak stabil** dan mempunyai lokaliti cache yang buruk, jadi sering lebih perlahan dalam amalan berbanding quicksort. Heap yang sama menjadi kekuatan **barisan keutamaan** dan mencari elemen top-k.

## Mengapa ia penting

Heap sort adalah satu-satunya jenis sort biasa yang merupakan kes terburuk O(n log n) dan in-place, menjadikannya berharga dalam tetapan terbatas memori atau batas terjamin.

Struktur heap di bawah adalah berguna secara meluas — barisan keutamaan, algoritma Dijkstra, dan streaming top-k.

Ia mengukuhkan idea bahawa struktur data yang betul membuat algoritma cekap.