Hàng đợi ưu tiên (Priority Queue) trong C++

Queue thông thường là FIFO. Priority Queue là biến thể: mỗi phần tử có độ ưu tiên, xóa phần tử ưu tiên cao nhất trước. Cách dễ nhất triển khai là dùng heap.

Trong C++ STL, priority_queue mặc định ưu tiên giá trị lớn hơn (max-heap).

Thuật toán

insert(key, priority):
    thêm key vào cuối heap
    heapify theo priority

delete():
    item = root
    root = phần tử cuối
    heapify lại
    return item

Ví dụ sử dụng STL priority_queue

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

void hienThi(priority_queue<int> q) {
    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;
}

int main() {
    priority_queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    q.push(5);
    q.push(1);
    
    cout << "Queue hiện tại: "; hienThi(q);
    cout << "Kích thước: " << q.size() << endl;
    cout << "Phần tử đầu (max): " << q.top() << endl;
    
    cout << "Xóa phần tử max: "; q.pop(); hienThi(q);
    cout << "Xóa phần tử max: "; q.pop(); hienThi(q);
    
    return 0;
}

Kết quả chạy chương trình

Queue hiện tại: 30 20 10 5 1
Kích thước: 5
Phần tử đầu (max): 30
Xóa phần tử max: 20 10 5 1
Xóa phần tử max: 10 5 1