STL Priority Queue cho Struct/Class trong C++

Ví dụ: Priority Queue cho struct Student

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Student {
    int roll, marks;
    Student(int r, int m) : roll(r), marks(m) {}
};

// Comparator: ưu tiên marks CAO hơn -> top là marks lớn nhất
// priority_queue dùng less mặc định -> top là MAX.
// Với custom comparator: trả về true nếu a kém hơn b (a "nhỏ hơn" b).
struct CompareMarks {
    bool operator()(const Student& a, const Student& b) const {
        return a.marks < b.marks; // a kém hơn b khi marks nhỏ hơn -> max-heap theo marks
    }
};

int main() {
    // Cú pháp đầy đủ: priority_queue
    priority_queue<Student, vector<Student>, CompareMarks> pq;

    int data[6][2] = {{15,50}, {16,60}, {18,70}, {14,80}, {12,90}, {20,100}};
    for (auto& d : data) pq.emplace(d[0], d[1]);

    cout << "Priority queue (max marks first):\n";
    while (!pq.empty()) {
        Student s = pq.top(); pq.pop();
        cout << s.roll << ' ' << s.marks << '\n';
    }
    return 0;
}

Kết quả

Priority queue (max marks first):
20 100
12 90
14 80
18 70
16 60
15 50

Giải thích comparator

Mẹo nhớ: Comparator giống như std::less cho max-heap. priority_queue đặt phần tử "lớn nhất" theo comparator lên top.

Dùng Lambda (C++11)

auto cmp = [](const Student& a, const Student& b) { return a.marks < b.marks; };
priority_queue<Student, vector<Student>, decltype(cmp)> pq(cmp);

Lưu ý quan trọng

• Comparator phải là Strict Weak Ordering (bán thứ tự chặt).
• Struct/class nên có constructor, hoặc dùng emplace.
• Không thể duyệt priority_queue (không có iterator) – chỉ top(), pop(), push().
• Cần duyệt sorted → đổ ra vector rồi sort, hoặc dùng std::multiset.

Ứng dụng thực tế

• Thuật toán Dijkstra, A* (min-heap distance).
• Huffman coding (min-heap frequency).
• Task scheduling (priority-based).
• K largest/smallest elements (streaming).