Wiki › Cấu trúc dữ liệu › Cây › Heap / Hàng đợi ưu tiên

Heap / Hàng đợi ưu tiên

huunguyen Updated Tháng sáu 2, 2026

Heap (đống) là cấu trúc dữ liệu giúp ta luôn lấy ra được phần tử lớn nhất (max-heap) hoặc nhỏ nhất (min-heap) trong tập hợp một cách nhanh chóng, đồng thời cho phép thêm và xoá phần tử động. Nó được dùng để hiện thực hàng đợi ưu tiên (priority queue).

Nếu dùng mảng thường, mỗi lần tìm cực trị mất $O (N)$ ; còn nếu giữ mảng luôn sắp xếp thì mỗi lần chèn mất $O (N)$ . Heap dung hoà cả hai: push và pop chỉ tốn $O (\log N)$ , còn lấy cực trị top chỉ $O (1)$ . Đây là "vũ khí" nền tảng cho Dijkstra, thuật toán Huffman, mô phỏng theo sự kiện, và bài toán "K phần tử lớn nhất".

Ý tưởng / Trực giác

Heap là một cây nhị phân hoàn chỉnh (complete binary tree): mọi tầng đều đầy, trừ tầng cuối được lấp từ trái sang phải. Tính chất "hoàn chỉnh" cực kỳ quan trọng vì nó khiến chiều cao cây luôn là $⌊ \log_{2} N ⌋$ , và cho phép lưu cây bằng một mảng phẳng mà không cần con trỏ: nút ở chỉ số $i$ (đánh số từ 0) có con trái ở $2 i + 1$ , con phải ở $2 i + 2$ , và cha ở $⌊ (i - 1) / 2 ⌋$ .

Heap tuân theo tính chất đống (heap property): với max-heap, mỗi nút luôn $\geq$ các con của nó. Lưu ý đây là điều kiện yếu hơn cây tìm kiếm — heap không sắp thứ tự trái/phải, chỉ ràng buộc quan hệ cha–con. Chính vì ràng buộc lỏng này mà việc duy trì heap rẻ hơn nhiều so với giữ mảng sắp xếp.

Vì sao push/pop chỉ tốn $O (\log N)$ ? Khi cấu trúc bị phá vỡ tại một vị trí, ta chỉ cần sửa lại dọc theo một đường đi từ nút đó lên gốc hoặc xuống lá. Đường này dài tối đa bằng chiều cao cây $= O (\log N)$ .

push (sift-up / lên trên): đặt phần tử mới vào cuối mảng (giữ tính hoàn chỉnh), rồi liên tục so với cha; nếu lớn hơn cha thì đổi chỗ, đi lên cho tới khi đúng vị trí.
pop (sift-down / xuống dưới): gốc là cực trị cần lấy ra; ta đưa phần tử cuối lên thay gốc rồi liên tục đổi nó với con lớn hơn cho tới khi tính chất đống được khôi phục.

Ví dụ chạy tay

Ta xây max-heap bằng cách push lần lượt các số [3, 1, 4, 1, 5, 9]. Mảng lưu heap đặt chỉ số từ 0; ta vẽ cả mảng và cây tương ứng.

push 3 rồi push 1 (1 < cha 3, đứng yên), rồi push 4:

push 4: đặt 4 vào cuối (index 2), cha = (2-1)/2 = 0 -> phần tử 3
mảng: [3, 1, 4]
                       4 > 3  => SIFT-UP, đổi chỗ
mảng: [4, 1, 3]

cây:        4
           / \
          1   3

push 1 (vào index 3, cha = index 1 = giá trị 1; 1 không > 1 nên đứng yên):

mảng: [4, 1, 3, 1]
              ^ phần tử mới
cây:        4
           / \
          1   3
         /
        1

push 5 (vào index 4, cha = index 1 = giá trị 1):

mảng: [4, 1, 3, 1, 5]
                  ^ mới, 5 > cha 1 => SIFT-UP
mảng: [4, 5, 3, 1, 1]      (5 lên index 1; 5 > gốc 4 => SIFT-UP tiếp)
mảng: [5, 4, 3, 1, 1]

cây:        5
           / \
          4   3
         / \
        1   1

push 9 (vào index 5, cha = index 2 = giá trị 3):

mảng: [5, 4, 3, 1, 1, 9]
                     ^ mới, 9 > cha 3 => SIFT-UP
mảng: [5, 4, 9, 1, 1, 3]   (9 lên index 2; 9 > gốc 5 => SIFT-UP tiếp)
mảng: [9, 4, 5, 1, 1, 3]

cây:        9            <- gốc luôn là cực đại
           / \
          4   5
         /|   |
        1 1   3

Bây giờ thực hiện pop (lấy ra 9). Đưa phần tử cuối (3) lên gốc, bỏ phần tử cuối, rồi SIFT-DOWN:

lấy 9 ra. mảng: [3, 4, 5, 1, 1]
gốc = 3, hai con là 4 (index 1) và 5 (index 2)
con lớn hơn là 5; 3 < 5 => đổi 3 với 5
mảng: [5, 4, 3, 1, 1]
                ^ 3 xuống index 2, không còn con => dừng

cây:        5            <- cực đại tiếp theo nổi lên gốc
           / \
          4   3
         / \
        1   1

Quan sát mấu chốt: mỗi thao tác chỉ chạm vào các nút trên một đường thẳng đứng trong cây, nên rất nhanh.

Cài đặt

Trong thi đấu hầu như luôn dùng priority_queue của STL thay vì tự viết. Nhưng nên hiểu cài đặt thủ công để biết nó hoạt động ra sao.

Dùng STL (khuyến nghị)

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Max-heap: top() là phần tử LỚN NHẤT (mặc định)
    priority_queue<int> maxpq;
    maxpq.push(3); maxpq.push(1); maxpq.push(4);
    cout << maxpq.top() << "\n";   // 4

    // Min-heap: thêm greater<int> để đảo so sánh
    priority_queue<int, vector<int>, greater<int>> minpq;
    minpq.push(3); minpq.push(1); minpq.push(4);
    cout << minpq.top() << "\n";   // 1

    // Heap theo cặp: mặc định so sánh theo phần tử đầu rồi phần tử sau
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;  // min-heap theo first
    pq.push({5, 0});
    pq.push({2, 1});
    cout << pq.top().second << "\n"; // 1 (vì 2 < 5)
    return 0;
}

Tự cài max-heap (sift-up / sift-down)

struct MaxHeap {
    vector<long long> h;            // h[0] là gốc = phần tử lớn nhất

    void push(long long x) {
        h.push_back(x);             // đặt vào cuối (giữ cây hoàn chỉnh)
        int i = h.size() - 1;
        while (i > 0) {
            int p = (i - 1) / 2;    // chỉ số cha
            if (h[p] >= h[i]) break;// cha đã >= con => đúng vị trí
            swap(h[p], h[i]);       // SIFT-UP: đổi với cha
            i = p;
        }
    }

    long long top() { return h[0]; }

    void pop() {
        h[0] = h.back();            // đưa phần tử cuối lên gốc
        h.pop_back();
        int i = 0, n = h.size();
        while (true) {
            int l = 2*i + 1, r = 2*i + 2, big = i;
            if (l < n && h[l] > h[big]) big = l;
            if (r < n && h[r] > h[big]) big = r; // chọn con LỚN hơn
            if (big == i) break;    // không vi phạm nữa => dừng
            swap(h[i], h[big]);     // SIFT-DOWN
            i = big;
        }
    }

    bool empty() { return h.empty(); }
    int  size()  { return h.size(); }
};

Xây heap từ mảng có sẵn trong $O (N)$

Nếu đã có sẵn cả mảng, đừng push từng phần tử ( $O (N \log N)$ ). Hãy gọi make_heap (hoặc tự sift-down từ nửa cuối mảng về đầu), chỉ tốn $O (N)$ :

vector<int> a = {3, 1, 4, 1, 5, 9};
make_heap(a.begin(), a.end());     // O(N), max-heap, a[0] = 9

Python

import heapq

h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
print(h[0])        # 1  (heapq là MIN-heap)
heapq.heappop(h)

# Max-heap: đẩy giá trị ÂM rồi đảo dấu khi lấy ra
heapq.heappush(h, -5)
print(-h[0])       # 5

a = [3, 1, 4, 1, 5]
heapq.heapify(a)   # O(N)

Độ phức tạp

Thao tác	Thời gian	Vì sao
`top`	$O (1)$	Cực trị luôn nằm ở gốc = `h[0]`, đọc trực tiếp.
`push`	$O (\log N)$	Sift-up đi tối đa từ lá tới gốc, dài bằng chiều cao $\log N$ .
`pop`	$O (\log N)$	Sift-down cũng đi dọc một đường tới lá, dài $\log N$ .
Xây từ mảng (`heapify`)	$O (N)$	Tổng chi phí sift-down: nhiều nút ở gần đáy chỉ đi vài bước; tổng $\sum_{h} \frac{N}{2^{h + 1}} \cdot h = O (N)$ .

Bộ nhớ: $O (N)$ — chỉ cần một mảng chứa $N$ phần tử, không có con trỏ phụ vì quan hệ cha–con suy ra từ chỉ số.

Lưu ý heap không hỗ trợ tìm kiếm một phần tử bất kỳ trong $O (\log N)$ (đó là việc của cây tìm kiếm cân bằng); tìm phần tử bất kỳ trong heap vẫn là $O (N)$ .

⚠️ Lỗi thường gặp

Nhầm max-heap với min-heap. priority_queue<int> của C++ là max-heap (lấy lớn nhất), trong khi heapq của Python là min-heap (lấy nhỏ nhất). Quên greater<int> (C++) hay quên đảo dấu (Python) là lỗi rất phổ biến. Triệu chứng: đáp án "ngược" hoàn toàn. Hãy viết một test 2–3 phần tử kiểm tra top() trước khi tin tưởng.
Tràn số khi cộng dồn. Trong các bài kiểu Huffman/mergefruit, tổng chi phí có thể tới $N \times max a_{i} \approx 10^{5} \times 2 \cdot 10^{4} = 2 \cdot 10^{9}$ , vượt int (giới hạn $\approx 2.1 \cdot 10^{9}$ rất sát, dễ tràn). Luôn dùng long long cho biến tổng và cho kiểu phần tử trong heap nếu chúng được cộng lại. Triệu chứng: đúng test nhỏ, sai/âm ở test lớn.
Sai thứ tự ưu tiên của pair/tuple. priority_queue<pair<...>> so sánh theo first rồi mới tới second. Nếu muốn ưu tiên theo "khối lượng" thì khối lượng phải nằm ở first; đặt nhầm thứ tự trường sẽ ra heap sai khoá. Với Dijkstra, nhớ để khoảng cách ở first, đỉnh ở second.
Gọi top()/pop() khi heap rỗng. Đây là hành vi không xác định (undefined behavior), có thể crash hoặc trả rác. Luôn kiểm tra !pq.empty() trước. Triệu chứng: RE (runtime error) hoặc kết quả ngẫu nhiên.
Dùng heap khi đã có sẵn cả mảng nhưng push từng cái. Tốn $O (N \log N)$ thay vì make_heap/heapify $O (N)$ . Không sai kết quả nhưng có thể TLE ở ràng buộc lớn.
Tưởng heap đã sắp xếp. Duyệt mảng heap từ trái sang phải không ra dãy có thứ tự. Muốn dãy sắp xếp phải pop lần lượt (đó chính là Heapsort, $O (N \log N)$ ).

Biến thể / Mở rộng

Hàng đợi ưu tiên có giảm khoá (decrease-key): Dijkstra/Prim cần giảm khoá của một đỉnh. Mẹo phổ biến là "lazy deletion": không sửa phần tử cũ, mà push bản mới rồi khi pop thì bỏ qua bản đã lỗi thời (kiểm tra if (d > dist[u]) continue;).
Hai heap để lấy trung vị động (median): một max-heap giữ nửa nhỏ, một min-heap giữ nửa lớn; cân bằng kích thước để trung vị luôn ở đỉnh.
K phần tử lớn nhất: dùng min-heap kích thước $K$ , đẩy vào rồi nếu quá $K$ thì pop phần tử nhỏ nhất; cuối cùng heap chứa đúng K phần tử lớn nhất, tốn $O (N \log K)$ .

// K phần tử lớn nhất bằng min-heap kích thước K
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : a) {
    pq.push(x);
    if ((int)pq.size() > k) pq.pop(); // loại phần tử nhỏ nhất hiện có
}
// pq chứa K phần tử lớn nhất; pq.top() là phần tử lớn thứ K

Heap còn là xương sống của Dijkstra (xem trang Đồ thị / đường đi ngắn nhất) và mã hoá Huffman.

Bài tập luyện

Pha Chế Nguyên Liệu (mergefruit) — (Intermediate) Huffman cơ bản: luôn lấy hai đống nhỏ nhất bằng min-heap rồi gộp, ví dụ vào sách giáo khoa của priority queue.
Hội nghị II (convention2) — (Intermediate) Mô phỏng theo sự kiện: dùng heap chọn con bò thâm niên nhất đang chờ để tính thời gian chờ tối đa.
Phiếu Giảm Giá Bò (cowcoup) — (Veteran) Tham lam kết hợp heap: dùng phiếu cho những con lợi nhất, quản lý tập "tiết kiệm được" bằng hàng đợi ưu tiên.
Cải tạo vườn hoa (landscape) — (Expert) Tham lam + heap nâng cao (Slope Trick / regret heap): luyện tư duy dùng đống để hối tiếc và đảo lựa chọn.
Đàn Bò Robot (roboherd) — (Master) Sinh K tổ hợp nhỏ nhất bằng heap kết hợp chặt nhị phân — bài tổng hợp khó, ép dùng heap để duyệt trạng thái theo thứ tự giá trị.