Hàng đợi ưu tiên của cặp (Priority Queue of Pairs) trong C++ (Sắp xếp theo first)

Priority Queue là cấu trúc dữ liệu trừu tượng lưu trữ các phần tử có độ ưu tiên, hỗ trợ lấy phần tử ưu tiên cao nhất (max-heap mặc định) hoặc thấp nhất (min-heap).

Khi lưu trữ pair<int,int>, mặc định so sánh theo first, nếu bằng thì so sánh second (lexicographical).

1. Max Priority Queue (Max Heap) - Mặc định

Phần tử có first lớn nhất ở đỉnh.

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

int main() {
    priority_queue<pair<int,int>> pq;
    pq.push({18, 200});
    pq.push({29, 100});
    pq.push({11, 400});
    auto top = pq.top(); // {29, 100} vì 29 lớn nhất
    cout << top.first << " " << top.second; // 29 100
    return 0;
}

2. Min Priority Queue (Min Heap)

Dùng greater<pair<int,int>> làm comparator. Phần tử first nhỏ nhất ở đỉnh.

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

int main() {
    using pii = pair<int,int>;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({10, 200});
    pq.push({20, 100});
    pq.push({15, 400});
    auto top = pq.top(); // {10, 200} vì 10 nhỏ nhất
    cout << top.first << " " << top.second; // 10 200
    return 0;
}

Các hàm thường dùng

• push(x): thêm phần tử.
• top(): truy cập phần tử đỉnh (không xóa).
• pop(): xóa phần tử đỉnh.
• size(), empty().

Lưu ý: Không hỗ trợ duyệt (iterator) hay xóa phần tử tùy ý.