Heap & Priority Queue
Binary Heap, thao tác heapify, và ứng dụng thực tế: task scheduling, top-K, và nền tảng cho thuật toán Dijkstra (Module 10).
Khi cần xử lý "phần tử ưu tiên nhất" liên tục (không phải theo thứ tự vào như Queue thường), Heap là cấu trúc dữ liệu chuẩn — xuất hiện trong task scheduler của hệ điều hành, thuật toán tìm đường đi ngắn nhất, và vô số bài toán "top-K" phổ biến trong xử lý dữ liệu thực tế.
🎯 Mục tiêu học tập
- Hiểu cấu trúc Binary Heap và bất biến (heap property) nó duy trì
- Triển khai các thao tác cơ bản: insert, extract-min/max, heapify
- Ứng dụng Heap cho bài toán Top-K hiệu quả hơn sắp xếp toàn bộ
- Nhận diện các ứng dụng thực tế của Priority Queue trong hệ thống backend
Binary Heap — cấu trúc & Bất biến
Min-Heap (hoặc Max-Heap) là cây nhị phân gần hoàn chỉnh (complete binary tree) duy trì
bất biến: mỗi node luôn nhỏ hơn (hoặc lớn hơn với Max-Heap) cả 2 con của nó — không đòi
hỏi thứ tự nghiêm ngặt như BST (Module 3), chỉ cần đúng quan hệ cha-con. Bất biến yếu hơn này cho phép
triển khai cực kỳ gọn nhẹ bằng 1 mảng đơn giản (không cần con trỏ node như cây thường) —
với node tại index i, con trái ở 2i+1, con phải ở 2i+2, cha ở (i-1)//2.
import heapq
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 8)
heapq.heappop(min_heap) # trả về 2 — phần tử nhỏ nhất, O(log n)
min_heap[0] # xem phần tử nhỏ nhất mà không lấy ra, O(1)
Thao tác push/pop đều O(log n) (do cần "sửa" lại bất biến heap bằng cách
"nổi lên"/"chìm xuống" qua các tầng của cây — chiều cao cây là log n), nhưng xem phần tử nhỏ
nhất/lớn nhất luôn O(1) — đây chính xác là điều Priority Queue cần: truy cập nhanh vào phần tử
ưu tiên cao nhất, không cần sắp xếp toàn bộ.
Bài toán Top-K — ứng dụng kinh điển
Bài toán phổ biến: tìm K phần tử lớn nhất trong N phần tử (N rất lớn). Cách "ngây thơ" — sắp xếp toàn bộ rồi lấy K phần tử đầu — tốn O(N log N). Dùng Min-Heap kích thước cố định K: duyệt qua từng phần tử, nếu heap chưa đủ K phần tử thì thêm vào, nếu đã đủ và phần tử mới lớn hơn phần tử nhỏ nhất trong heap thì thay thế — độ phức tạp giảm còn O(N log K), nhanh hơn đáng kể khi K nhỏ hơn nhiều so với N (ví dụ: tìm 10 sản phẩm bán chạy nhất trong 10 triệu giao dịch).
import heapq
def top_k_lon_nhat(nums: list[int], k: int) -> list[int]:
min_heap = []
for num in nums:
if len(min_heap) < k:
heapq.heappush(min_heap, num)
elif num > min_heap[0]:
heapq.heapreplace(min_heap, num) # pop rồi push trong 1 thao tác
return min_heap
Ứng dụng thực tế khác của Priority Queue
- Task Scheduling: hệ điều hành/scheduler chọn tiến trình có độ ưu tiên cao nhất để chạy tiếp theo — chính là extract-max liên tục trên 1 heap.
- Thuật toán Dijkstra (Module 10): luôn cần chọn node "gần nhất chưa thăm" tiếp theo — Priority Queue là cấu trúc dữ liệu tiêu chuẩn triển khai bước này hiệu quả.
- Merge K Sorted Lists: hợp nhất nhiều danh sách đã sắp xếp (ví dụ kết quả từ nhiều shard database — liên hệ khoá Architecture Module 7) thành 1 danh sách sắp xếp duy nhất, dùng heap để luôn biết phần tử nhỏ nhất tiếp theo trong số các danh sách.
- Rate Limiting theo độ ưu tiên: xử lý request VIP trước request thường, dùng Priority Queue thay vì Queue FIFO thông thường (Module 2).
🏋️ Bài tập thực hành
Với 1 tập dữ liệu lớn giả lập (ví dụ 100.000 số ngẫu nhiên), viết hàm tìm 10 số lớn nhất bằng Min-Heap kích thước 10, đo thời gian chạy. So sánh với cách sắp xếp toàn bộ rồi lấy 10 phần tử đầu, đo thời gian chạy của cả 2 cách và xác nhận bằng số liệu thật rằng cách dùng Heap nhanh hơn khi K nhỏ hơn nhiều so với N.
📚 Tài nguyên học tập
-
VisuAlgo — HeapTrực quan hoá tương tác Binary HeapTool
-
Python — heapq module documentationTài liệu chính thức module heapq của PythonDocs
✅ Tự đánh giá hoàn thành
- Giải thích được heap property và cách biểu diễn heap bằng mảng
- Triển khai/dùng đúng insert và extract-min/max
- Giải quyết được bài toán Top-K với độ phức tạp O(N log K)
- Nhận diện được ít nhất 3 ứng dụng thực tế của Priority Queue