Heap là gì và nó hiện thực priority queue như thế nào?

Question

IT Interview Practice · Accepted Answer

**Binary heap** là một cây nhị phân đầy đủ (complete binary tree) được lưu trong một array, duy trì **thuộc tính heap (heap property)**: trong một **min-heap**, mọi cha (parent) đều ≤ các con của nó, nên **giá trị nhỏ nhất luôn ở root**. Điều này khiến nó là hiện thực tiêu chuẩn của một **priority queue** (hàng đợi ưu tiên).

## Bố cục array

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

## Các thao tác

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up (sủi lên)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — bỏ root, sift down (chìm xuống) -> 1
```

## Độ phức tạp

| Thao tác | Thời gian |
|---|---|
| peek min/max | O(1) |
| push (chèn) | O(log n) |
| pop (lấy ra) | O(log n) |
| build heap từ n phần tử | O(n) |

## Khi nào dùng

- **Lập lịch** theo độ ưu tiên (ví dụ bộ lập lịch tác vụ của OS).
- Thuật toán đường đi ngắn nhất và MST **Dijkstra / Prim**.
- Bài toán **Top-K** và trung vị trên luồng (streaming median).
- **Heap sort** (sắp xếp tại chỗ O(n log n)).

## Tại sao điều này quan trọng

Một heap cho bạn phần tử quan trọng tiếp theo ngay lập tức mà không cần giữ mọi thứ được sắp xếp hoàn toàn, điều này rẻ hơn nhiều so với sắp xếp lại.

Nó là xương sống của các thuật toán theo độ ưu tiên và là công cụ phỏng vấn thường gặp cho các câu hỏi "k lớn nhất/nhỏ nhất".

Thao tác	Thời gian
peek min/max	O(1)
push (chèn)	O(log n)
pop (lấy ra)	O(log n)
build heap từ n phần tử	O(n)

Bố cục array

Các thao tác

Độ phức tạp

Khi nào dùng

Tại sao điều này quan trọng

Câu hỏi liên quan