Hàng đợi ưu tiên (Priority Queue) trong thư viện STL của C++

Hàng đợi ưu tiên là một kiểu dữ liệu trừu tượng để lưu trữ tập hợp các phần tử có ưu tiên, hỗ trợ chèn và xóa phần tử dựa trên ưu tiên của chúng, nghĩa là phần tử có ưu tiên cao nhất có thể bị xóa bất cứ lúc nào. Hàng đợi ưu tiên không lưu trữ các phần tử theo kiểu tuyến tính liên quan đến vị trí của chúng như Stack, Queue, List, v.v. Hàng đợi ưu tiên ADT (kiểu dữ liệu trừu tượng) lưu trữ các phần tử dựa trên ưu tiên của chúng.

Hàng đợi ưu tiên hỗ trợ các hàm sau –

Size() – dùng để tính kích thước của hàng đợi ưu tiên vì nó trả về số lượng phần tử trong đó.

Empty() – trả về true nếu hàng đợi ưu tiên rỗng và false nếu ngược lại.

Insert(element) – dùng để chèn phần tử mới vào hàng đợi ưu tiên.

Min() – trả về phần tử có giá trị khóa nhỏ nhất liên kết và hiển thị thông báo lỗi nếu hàng đợi ưu tiên rỗng.

removeMin() – xóa phần tử được tham chiếu bởi hàm min().

Bảng dưới đây cho thấy tác động của các phép toán trên hàng đợi ưu tiên

Bắt đầu
Bước 1 -> Khai báo hàm hiển thị các phần tử trong hàng đợi ưu tiên
    void display(priority_queue <int> Pq)
    khai báo và gán priority_queue <int> que = Pq
    Vòng lặp Khi (!que.empty())
        gọi que.top()
        gọi que.pop()
    Kết thúc
Bước 2 -> Trong main()
    Tạo đối tượng priority_queue <int> Pq
    Gọi push() để chèn phần tử vào hàng đợi ưu tiên như Pq.push(1)
    Gọi display(Pq)
    Gọi để kiểm tra kích thước hàng đợi ưu tiên Pq.size()
    Gọi để hiển thị phần tử đầu hàng đợi ưu tiên Pq.top()
    Gọi để xóa phần tử hàng đợi ưu tiên Pq.pop()
    Gọi display(Pq)
Kết thúc

Ví dụ mã C++

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

void display(priority_queue <int> Pq) {
    priority_queue <int> que = Pq;
    while (!que.empty()) {
        cout << '\t' << que.top();
        que.pop();
    }
    //cout << '\n';
}

int main() {
    priority_queue <int> Pq;
    Pq.push(1);
    Pq.push(3);
    Pq.push(5);
    Pq.push(7);
    Pq.push(9);
    cout << "Hàng đợi ưu tiên là : ";
    display(Pq);
    cout << "\nKích thước hàng đợi ưu tiên dùng size() : " << Pq.size();
    cout << "\nPhần tử đầu hàng đợi ưu tiên dùng top(): " << Pq.top();
    cout << "\nxóa phần tử dùng pop() : ";
    Pq.pop();
    display(Pq);
    return 0;
}

Đầu ra

Hàng đợi ưu tiên là : 9 7 5 3 1
Kích thước hàng đợi ưu tiên dùng size() : 5
Phần tử đầu hàng đợi ưu tiên dùng top(): 9
xóa phần tử dùng pop() : 7 5 3 1