Apakah heap dan bagaimana ia melaksanakan antrian prioriti?

Question

Accepted Answer

**binary heap** adalah pohon biner lengkap yang disimpan dalam array yang mempertahankan **heap property**: dalam **min-heap**, setiap induk ≤ anaknya, jadi **minimum selalu berada di akar**. Ini menjadikannya 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

- **Scheduling** by priority (e.g. OS task schedulers).
- **Dijkstra / Prim** shortest-path and MST algorithms.
- **Top-K** problems and streaming medians.
- **Heap sort** (in-place O(n log n)).

## Mengapa penting

Heap memberikan anda item terpenting berikutnya secara instan tanpa menyimpan semuanya dengan sempurna terurut, yang jauh lebih murah daripada menyortir ulang.

Ia adalah tulang punggung algoritma yang didorong prioritas dan alat wawancara yang sering 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)