Apa itu heap dan bagaimana implementasinya menjadi antrian prioritas?

Question

IT Interview Practice · Accepted Answer

A **binary heap** adalah pohon biner lengkap yang disimpan dalam array yang mempertahankan **heap property**: dalam **min-heap**, setiap induk ≤ anak-anaknya, jadi **minimum selalu berada di akar**. Ini adalah implementasi standar dari **priority queue**.

## Array layout

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## Operations

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — remove root, sift down -> 1
```

## Complexity

| Operation | Time |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| build heap from n items | O(n) |

## When to use

- **Penjadwalan** berdasarkan prioritas (misalnya penjadwal tugas OS).
- Algoritma **Dijkstra / Prim** jalur terpendek dan MST.
- Masalah **Top-K** dan median streaming.
- **Heap sort** (in-place O(n log n)).

## Mengapa ini penting

Heap memberi Anda item terpenting berikutnya secara instan tanpa menyimpan semuanya sepenuhnya disortir, yang jauh lebih murah daripada penyortiran ulang.

Ini adalah tulang punggung algoritma berbasis prioritas dan alat wawancara yang sering digunakan untuk pertanyaan "k terbesar/terkecil".

Operation	Time
peek min/max	O(1)
push (insert)	O(log n)
pop (extract)	O(log n)
build heap from n items	O(n)

Array layout

Operations

Complexity

When to use

Mengapa ini penting

Pertanyaan terkait