Heap (Hàng đợi ưu tiên) — Heap (Priority Queue)
Heap là cây nhị phân gần hoàn chỉnh lưu trong mảng, duy trì một bất biến duy nhất: node cha luôn nhỏ hơn hoặc bằng node con (min-heap) hoặc lớn hơn hoặc bằng (max-heap). Nhờ đó phần tử nhỏ nhất/lớn nhất luôn nằm ở đỉnh — đọc ra O(1), còn thêm (push) hay lấy ra (pop) chỉ tốn O(log n) vì phần tử chỉ di chuyển dọc theo chiều cao cây.
Lưu ý quan trọng: heap KHÔNG sắp xếp toàn bộ — chỉ đảm bảo quan hệ cha–con. Duyệt mảng bên trong heap sẽ không cho thứ tự tăng dần.
JavaScript không có heap built-in (khác Python heapq hay Java PriorityQueue), nên trong phỏng vấn bạn cần tự cài bằng mảng: cha ở chỉ số i, hai con ở 2i+1 và 2i+2; push thì "nổi lên" (sift up), pop thì "chìm xuống" (sift down).
Như phòng cấp cứu bệnh viện — bệnh nhân nặng nhất luôn được gọi trước, bất kể ai đến trước.
Danh sách chờ không cần sắp xếp toàn bộ; chỉ cần biết chính xác ai đang đứng đầu, và cập nhật nhanh khi có người mới vào hoặc người đầu được gọi đi.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Heap (Hàng đợi ưu tiên)
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| top K phần tử | Heap kích thước K thay vì sort cả mảng |
| lớn thứ K / nhỏ thứ K | Min-heap giữ đúng K phần tử, đỉnh là đáp án |
| lấy max/min liên tục từ dòng dữ liệu | push/pop O(log n) — không cần sort lại mỗi lần |
| gộp K danh sách đã sắp xếp | Heap K phần tử luôn cho phần tử nhỏ nhất kế tiếp |
| median động | Hai heap: max-heap nửa dưới + min-heap nửa trên |
Khi nào dùng
4 tình huống điển hình cần nghĩ đến chủ đề này
Cần lấy min/max NHIỀU LẦN trong khi dữ liệu liên tục thay đổi (thêm/bớt phần tử)
Bài dạng "top k" — k phần tử lớn nhất/nhỏ nhất/xuất hiện nhiều nhất
Gộp k nguồn dữ liệu đã sắp xếp (merge k sorted lists)
Duy trì trung vị hoặc thống kê thứ hạng trên luồng dữ liệu chảy vào liên tục
Lập lịch theo độ ưu tiên: task scheduler, Dijkstra chọn đỉnh gần nhất
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Chỉ cần max/min đúng 1 lần trên dữ liệu tĩnh → duyệt mảng O(n) là đủ, dựng heap là thừa
Cần truy cập phần tử bất kỳ theo thứ hạng (phần tử thứ i bất kỳ) → sort một lần O(n log n) rồi đánh chỉ số
Cần tìm kiếm một giá trị cụ thể có tồn tại hay không → hash map O(1), heap phải quét O(n)
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function heapPattern(nums: number[], k: number): R {
const heap = new MinHeap() // JS không có sẵn — tự cài hoặc dùng mảng + sort chèn
for (const x of nums) {
heap.push(x)
// Giữ heap đúng k phần tử → đỉnh heap là phần tử lớn thứ k
if (heap.size() > k) heap.pop()
}
return heap.peek()
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
Heap lưu trong mảng: cha tại i, con tại 2i+1 và 2i+2 — không cần con trỏ
Chỉ đỉnh heap được đảm bảo là min/max; phần còn lại KHÔNG sắp xếp toàn phần
Pattern "top k": min-heap kích thước k giữ k phần tử lớn nhất → O(n log k) thay vì sort O(n log n)
Hai heap (max-heap nửa dưới + min-heap nửa trên) duy trì trung vị luồng dữ liệu trong O(log n) mỗi thao tác
Lỗi thường gặp
Nhầm heap là mảng đã sắp xếp toàn phần — duyệt mảng bên trong heap không cho thứ tự tăng dần
Quên JavaScript không có heap built-in — nên luyện cài sift up/sift down trước khi vào phỏng vấn
Tìm k phần tử LỚN nhất nhưng dùng max-heap kích thước k (đúng ra là min-heap để loại phần tử nhỏ nhất khi vượt k)
Quên check heap rỗng trước khi pop/peek → undefined
Độ phức tạp
push/pop O(log n), peek O(1)Bài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay