Heap & hàng đợi ưu tiên

Bạn sẽ học được gì

Heap là cấu trúc luôn cho bạn lấy ra phần tử nhỏ nhất (hoặc lớn nhất) tức thì — nền của hàng đợi ưu tiên (priority queue). Bạn sẽ hiểu tính chất heap, cách lưu gọn trong mảng, và vì sao thêm/xóa là O(log n).

1. Trực quan: phòng cấp cứu ưu tiên người nặng nhất

Queue thường phục vụ theo thứ tự đến (FIFO). Nhưng phòng cấp cứu phục vụ theo mức độ nặng, bất kể đến trước sau. Đó là hàng đợi ưu tiên — và heap là cách cài hiệu quả nhất.

Min-heap: cây nhị phân đầy đủ (lấp đầy trái sang phải) thỏa tính chất: mỗi nút ≤ các con của nó. Hệ quả: nhỏ nhất luôn ở gốc.

        ┌───┐
        │ 1 │  ← gốc = nhỏ nhất
        └─┬─┘
      ┌───┴───┐
    ┌─┴─┐   ┌─┴─┐
    │ 3 │   │ 5 │      mỗi cha ≤ con
    └─┬─┘   └───┘
   ┌──┴┐
 ┌─┴─┐ ┌─┴─┐
 │ 7 │ │ 4 │
 └───┘ └───┘

2. Mẹo: heap lưu gọn trong MẢNG (không cần con trỏ)

Vì heap là cây đầy đủ, ta lưu nó trong một mảng theo thứ tự lớp. Quan hệ cha–con tính bằng công thức chỉ số:

nút ở chỉ số i:
  con trái  = 2*i + 1
  con phải  = 2*i + 2
  cha       = (i - 1) // 2

Heap trên = mảng: [1, 3, 5, 7, 4]
            chỉ số:  0  1  2  3  4

Không cần con trỏ — chỉ cần phép tính chỉ số. Gọn và cache tốt.

3. Các thao tác

Thao tác	Ý nghĩa	Độ phức tạp
peek	xem nhỏ nhất (gốc)	O(1)
push	thêm phần tử	O(log n)
pop	lấy & bỏ nhỏ nhất	O(log n)

push/pop là O(log n) vì phần tử chỉ "đi lên/xuống" theo chiều cao cây (~log n).

🎬 Trực quan hóa tương tác — VisuAlgo

Trực quan hóa push (sift-up) và pop (sift-down) từng bước. Quan sát mảng và cây thay đổi song song.

Xem Heap animation ↗

Nguồn: visualgo.net — Steven Halim, NUS. Dùng cho lớp học; ảnh chụp/video cần ghi nguồn URL.

4. Chạy debug: push 2 (sift-up)

Thêm phần tử: đặt vào cuối rồi cho nó nổi lên (sift-up) — đổi chỗ với cha khi nhỏ hơn cha, tới khi đúng vị trí. Bước qua việc push 2 vào heap [1, 3, 5, 7]:

🐞 push 2 vào min-heap [1, 3, 5, 7]Bước 1/5

1heap.append(2)          # dat vao cuoi (chi so 4)
2i = 4
3while i > 0:
4  cha = (i - 1) // 2
5  if heap[i] < heap[cha]:
6      doi_cho(i, cha)     # noi len
7      i = cha
8  else:
9      break

Biến tại bước này

heap	[1, 3, 5, 7, 2]
i	4

👉 Đặt 2 vào cuối (chỉ số 4).

Pop (lấy nhỏ nhất) làm ngược lại: đưa phần tử cuối lên gốc rồi cho nó chìm xuống (sift-down).

5. Code mẫu: dùng heapq của Python

Đang tải trình chạy code…

heapq là min-heap. Muốn max-heap: đẩy số âm (-x) hoặc dùng mẹo phủ định.

6. Dùng heap để làm gì?

• Lấy min/max liên tục: lịch trình, Dijkstra (đường đi ngắn nhất — Trụ 3).
• Top-K: tìm K phần tử lớn nhất/nhỏ nhất hiệu quả.
• Heap sort: sắp xếp bằng heap (Trụ 3).
• Hợp nhất nhiều dãy đã sắp xếp.

7. 🎮 Trò chơi: Hiểu heap

🎮 Hiểu heapCâu 1/4· Điểm 0· 🔥 0

Min-heap: cha ≤ con, nhỏ nhất ở gốc. Lưu trong mảng: con = 2i+1, 2i+2.

Lấy phần tử nhỏ nhất (peek) tốn?

8. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Heap dùng để cài cấu trúc nào?

2. Vì sao heap lưu được trong mảng mà không cần con trỏ?

3. heapq trong Python là loại heap gì?

📚 Đọc thêm & Luyện tập

🎬 Video

• William Fiset — Heap / Priority Queue (playlist) — Triển khai min-heap từ đầu, sift-up/down chi tiết
• NeetCode — Heap / Priority Queue — Giải thích ngắn + các bài LeetCode heap

🏋️ Luyện tập

• LeetCode — tag: Heap (Priority Queue) — Top-K, lịch trình, merge sorted lists

9. Hoàn thành

…

☑️ Tiếp theo: 2.5.6 — Trie (cây tiền tố).