PRIORITY QUEUE
HÀNG ĐỢI ƯU TIÊN - HEAP

Priority queue là gì?

priority_queue là hàng đợi ưu tiên. Mỗi lần lấy phần tử, ta không lấy theo thứ tự vào trước ra trước như queue, mà lấy phần tử có độ ưu tiên cao nhất.

Trong C++, priority_queue được cài đặt bằng cấu trúc heap. Mặc định là max-heap, nghĩa là phần tử lớn nhất nằm ở đỉnh.

Heap max và heap min

Heap max: phần tử ở đỉnh là lớn nhất. Đây là mặc định của priority_queue<int>.

Heap min: phần tử ở đỉnh là nhỏ nhất. Dùng dạng priority_queue<int, vector<int>, greater<int>>.

Heap max mặc định

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

priority_queue<int> pq;
priority_queue<long long> pq2;
priority_queue<double> pq3;

pq.top() luôn trả về phần tử lớn nhất hiện có.

Heap min

priority_queue<int, vector<int>, greater<int>> pq;

// Với pair:
priority_queue<
  pair<int, int>,
  vector<pair<int, int>>,
  greater<pair<int, int>>
> q;

pq.top() trả về phần tử nhỏ nhất.

Ví dụ 1. Heap max

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

int main() {
    priority_queue<int> pq;
    pq.push(3);
    pq.push(5);
    pq.push(1);

    cout << pq.top() << "\n"; // 5
    pq.pop();
    cout << pq.top() << "\n"; // 3
}

Ví dụ 2. Heap min

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

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(3);
    pq.push(5);
    pq.push(1);

    cout << pq.top() << "\n"; // 1
    pq.pop();
    cout << pq.top() << "\n"; // 3
}

1. Heap sort

Đưa toàn bộ phần tử vào heap rồi lấy dần ra để tạo dãy có thứ tự.

2. Bài toán ghép tối ưu

Luôn ghép hai phần tử nhỏ nhất trước, ví dụ bài cắt gỗ/Huffman.

3. K phần tử nhỏ nhất

Dùng heap để lấy dần k ứng viên tốt nhất mà không cần sinh toàn bộ tổ hợp.

4. Dijkstra

Lấy đỉnh có khoảng cách tạm thời nhỏ nhất bằng min-heap.

5. Mô phỏng sự kiện

Sự kiện nào có thời điểm nhỏ nhất thì xử lý trước.

6. Truy vấn online

Dữ liệu thay đổi liên tục, cần lấy max/min nhanh.