thuattoan.dev

Level 2 · Cấu trúc dữ liệu

Heap / Priority queue

Binary heap, heapify, ứng dụng Dijkstra/top-K.

Độ khó: Trung bình Visualizer tương tác6 bài luyện tập

Ý tưởng chính

Heap là cây nhị phân gần đầy cho phép lấy phần tử nhỏ nhất/lớn nhất trong O(log n), nền tảng cho hàng đợi ưu tiên.

Hình dung

Phòng cấp cứu: bệnh nhân không được khám theo thứ tự đến, mà ai nặng nhất được khám trước. Mỗi khi có người mới đến, y tá chỉ cần so với vài người để biết vị trí ưu tiên.

Cách hoạt động

  1. 1

    Heap là cây nhị phân gần đầy lưu trong mảng: con của i là 2i+1 và 2i+2, cha của i là (i−1)/2.

  2. 2

    Tính chất min-heap: mỗi nút nhỏ hơn hoặc bằng các con, nên gốc luôn là phần tử nhỏ nhất.

  3. 3

    push: thêm vào cuối mảng rồi "nổi lên" (so với cha, nhỏ hơn thì đổi chỗ).

  4. 4

    pop: lấy gốc, đưa phần tử cuối lên gốc rồi "chìm xuống" (đổi với con nhỏ hơn cho đến khi đúng chỗ).

Độ phức tạp

Xem phần tử nhỏ nhất O(1); push và pop O(log n); xây heap từ mảng bằng heapify O(n).

Khi nào dùng

Liên tục cần lấy phần tử nhỏ nhất/lớn nhất trong khi dữ liệu thay đổi: Dijkstra, top-K, lập lịch theo độ ưu tiên, trộn K danh sách.

Lỗi hay gặp

  • priority_queue trong C++ mặc định là max-heap; cần greater<> để có min-heap.
  • Nghĩ heap đã sắp xếp toàn bộ — chỉ có gốc chắc chắn là nhỏ nhất, các nút khác không theo thứ tự.

Liên hệ thực tế

Ứng dụng thực tế

Kỹ thuật này xuất hiện ở đâu ngoài đời — để bạn có sẵn một hình ảnh cụ thể khi học.

  • Lập lịch theo độ ưu tiên

    Hệ điều hành chọn tiến trình ưu tiên cao nhất, phòng cấp cứu xử lý ca nặng nhất trước — mỗi lần lấy phần tử "lớn nhất" trong O(log n).

  • Top-K trên luồng dữ liệu lớn

    10 bài hát nghe nhiều nhất, 100 từ khoá đang hot: chỉ cần giữ một min-heap kích thước K thay vì sắp xếp toàn bộ.

  • Bộ hẹn giờ (timer)

    Runtime của Go và thư viện libuv (nền của Node.js) lưu các timer trong heap để luôn biết timer nào sắp hết hạn.

  • Gộp nhiều file log theo thời gian

    Trộn K file đã sắp xếp: heap luôn cho biết dòng nào có timestamp nhỏ nhất trong K đầu file.

Xem thuật toán chạy

Minh hoạ từng bước

Chạy tự động hoặc đi từng bước; theo dõi hình minh hoạ, lời giải thích, giá trị biến và dòng code tương ứng cùng lúc.

Tự làm

Luyện tập trên Codeforces

Sắp xếp từ dễ đến khó theo rating, mỗi bài kèm tóm tắt đề. Bí thì mở gợi ý — có 3 mức, từ hướng suy nghĩ tới gần lời giải.

  • Rating 1000

    Powering the Hero (easy version)(mở Codeforces trong tab mới)

    Bộ bài có n lá: lá thưởng có sức mạnh > 0, lá anh hùng có sức mạnh 0. Rút lần lượt từ trên: lá thưởng có thể đặt lên chồng thưởng hoặc bỏ đi; lá anh hùng nhận sức mạnh của lá trên cùng chồng thưởng (lá đó bị bỏ) rồi vào quân đội. Tìm tổng sức mạnh quân đội lớn nhất (n ≤ 5000).

    Test mẫu & giải thích
    Input
    5
5
3 3 3 0 0
6
0 3 3 0 0 3
7
1 2 3 0 4 5 0
7
1 2 5 0 4 3 0
5
3 1 0 0 4
    Output
    6
6
8
9
4

    1. Test 1

      Ở test đầu n=5, dãy 3 3 3 0 0: ba lá thưởng đầu đều được giữ lại trên chồng (không lá nào cần bỏ) tạo chồng gồm ba lá giá trị 3; hai lá anh hùng liên tiếp sau đó lần lượt lấy lá trên cùng của chồng theo nguyên tắc ngăn xếp (LIFO), mỗi lần nhận đúng 3, tổng sức mạnh đạt 3+3=6, khớp đáp án.

    2. Test 2

      Ở test thứ hai, dãy 0 3 3 0 0 3: lá anh hùng đầu tiên gặp chồng rỗng nên nhận 0; hai lá thưởng giá trị 3 tiếp theo được giữ lại tạo chồng [3,3]; hai lá anh hùng kế tiếp lần lượt lấy đỉnh chồng, mỗi lần được 3, cộng dồn 0+3+3=6 (lá thưởng 3 cuối cùng không còn anh hùng nào để dùng nên bị bỏ phí), khớp đáp án 6.

  • Rating 1100

    Powering the Hero (hard version)(mở Codeforces trong tab mới)

    Giống bản dễ: rút lần lượt các lá, lá thưởng giữ hoặc bỏ, mỗi lá anh hùng nhận sức mạnh của một lá thưởng đứng trước nó. Tìm tổng sức mạnh lớn nhất, nhưng n lên tới 2·10⁵.

    Test mẫu & giải thích
    Input
    5
5
3 3 3 0 0
6
0 3 3 0 0 3
7
1 2 3 0 4 5 0
7
1 2 5 0 4 3 0
5
3 1 0 0 4
    Output
    6
6
8
9
4

    1. Test 1

      Ở test đầu n=5, dãy 3 3 3 0 0: ba lá thưởng đầu đều được giữ lại trên chồng (không lá nào cần bỏ) tạo chồng gồm ba lá giá trị 3; hai lá anh hùng liên tiếp sau đó lần lượt lấy lá trên cùng của chồng theo nguyên tắc ngăn xếp (LIFO), mỗi lần nhận đúng 3, tổng sức mạnh đạt 3+3=6, khớp đáp án.

    2. Test 2

      Ở test thứ hai, dãy 0 3 3 0 0 3: lá anh hùng đầu tiên gặp chồng rỗng nên nhận 0; hai lá thưởng giá trị 3 tiếp theo được giữ lại tạo chồng [3,3]; hai lá anh hùng kế tiếp lần lượt lấy đỉnh chồng, mỗi lần được 3, cộng dồn 0+3+3=6 (lá thưởng 3 cuối cùng không còn anh hùng nào để dùng nên bị bỏ phí), khớp đáp án 6.

  • Rating 1400

    Epic Transformation(mở Codeforces trong tab mới)

    Cho mảng a. Mỗi thao tác chọn hai phần tử có giá trị khác nhau và xoá cả hai. Tìm kích thước nhỏ nhất của mảng sau các thao tác.

    Test mẫu & giải thích
    Input
    5
6
1 6 1 1 4 4
2
1 2
2
1 1
5
4 5 4 5 4
6
2 3 2 1 3 1
    Output
    0
0
2
1
0

    1. Test 1

      Với test đầu, mảng [1,6,1,1,4,4] có tần suất: giá trị 1 xuất hiện 3 lần, 4 xuất hiện 2 lần, 6 xuất hiện 1 lần, n=6. Vì maxCount=3 không vượt quá phần còn lại (n-maxCount=3), toàn bộ 6 phần tử ghép hết theo cặp khác giá trị (ví dụ (1,6),(1,4),(1,4)), nên số phần tử thừa là n%2=0, khớp kết quả 0.

    2. Test 2

      Với test thứ hai, mảng [1,2] chỉ có 2 phần tử khác giá trị, ghép được đúng 1 cặp và xoá hết, còn lại 0, khớp dòng thứ hai của output.

  • Rating 1500

    Potions (Easy Version)(mở Codeforces trong tab mới)

    Có n lọ thuốc xếp hàng, lọ i thay đổi máu a_i (có thể âm). Bắt đầu với 0 máu, đi từ trái sang phải, uống hoặc bỏ qua từng lọ; máu không bao giờ được âm. Tìm số lọ uống được nhiều nhất (n ≤ 2000).

    Test mẫu & giải thích
    Input
    6
4 -4 1 -3 1 -3
    Output
    5

    Với a=[4,-4,1,-3,1,-3], mô phỏng greedy: uống 4 (máu=4), uống -4 (máu=0), uống 1 (máu=1), đến khi uống -3 thì máu tạm thời xuống -2<0 nên phải bỏ lại lọ có giá trị nhỏ nhất đã uống trước đó (chính là -4), máu hồi lại thành 2 và số lọ uống giảm xuống còn 3. Tiếp tục uống 1 (máu=3) rồi uống -3 (máu=0), hợp lệ. Tổng cộng uống được 5 trong 6 lọ (chỉ bỏ đúng lọ -4), khớp đáp số 5.

  • Rating 1600

    Potions (Hard Version)(mở Codeforces trong tab mới)

    Giống bản dễ: uống hoặc bỏ từng lọ thuốc từ trái sang phải, máu luôn không âm, tối đa hoá số lọ uống — nhưng n lên tới 2·10⁵.

    Test mẫu & giải thích
    Input
    6
4 -4 1 -3 1 -3
    Output
    5

    Cùng dữ liệu mẫu như bản dễ: a=[4,-4,1,-3,1,-3]. Duy trì tập lọ đã uống bằng cấu trúc dữ liệu hỗ trợ lấy phần tử nhỏ nhất để xử lý n lớn hiệu quả, nhưng logic giống hệt: uống lần lượt 4,-4,1 (máu=1), khi uống -3 máu xuống -2<0 nên loại bỏ lọ nhỏ nhất đã uống là -4 (máu hồi lại thành 2), rồi uống tiếp 1 (máu=3) và -3 (máu=0). Kết quả uống được 5/6 lọ, khớp đáp số 5.

  • Rating 2400

    Drazil Likes Heap(mở Codeforces trong tab mới)

    Cho max-heap độ cao h (2^h − 1 phần tử khác nhau). Thao tác f(i) xoá phần tử ở vị trí i bằng cách liên tục kéo con lớn hơn lên thế chỗ. Giảm heap xuống độ cao g (giữ đúng 2^g − 1 phần tử ở các vị trí đầu) sao cho tổng còn lại nhỏ nhất; in tổng và dãy thao tác.

    Test mẫu & giải thích
    Input
    2
3 2
7 6 3 5 4 2 1
3 2
7 6 5 4 3 2 1
    Output
    10
3 2 3 1
8
2 1 3 1

    Với test đầu (h=3,g=2), heap ban đầu a=[7,6,3,5,4,2,1] (1-indexed). Gọi f(3): con của nút3 là a6=2, a7=1, kéo 2 lên vị trí3, xoá nút6. Gọi f(2): con của nút2 là a4=5, a5=4, kéo 5 lên vị trí2, xoá nút4. Gọi f(3) lần nữa: nút3 lúc này chỉ còn một con là a7=1 (a6 đã bị xoá), kéo 1 lên vị trí3, xoá nút7. Gọi f(1): con của nút1 là a2=5, a3=1, kéo 5 lên vị trí1; nút2 lúc này chỉ còn con a5=4 nên kéo 4 lên vị trí2, xoá nút5. Heap còn lại {5,4,1}, tổng=10, khớp cả dãy thao tác "3 2 3 1" lẫn kết quả 10.