Rate this post

Priority Queue (hàng đợi ưu tiên) là một kiểu dữ liệu cấu trúc dữ liệu được sử dụng để quản lý các phần tử có ưu tiên. Mỗi phần tử trong hàng đợi ưu tiên được gán một ưu tiên và chỉ có phần tử có ưu tiên cao nhất mới được lấy ra từ hàng đợi.

Các bài viết liên quan:

Trong C++, có thể sử dụng STL (Standard Template Library) để tạo một priority queue. Ví dụ:

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

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

    cout << "Phan tu uu tien cao nhat: " << pq.top() << endl;
    pq.pop();
    cout << "Phan tu uu tien cao nhat sau khi xoa: " << pq.top() << endl;
    return 0;
}

Trong ví dụ trên, chúng ta đã tạo một priority queue sử dụng kiểu dữ liệu int. Chúng ta đã thêm các giá trị 5, 1, 10, 2 vào hàng đợi với ưu tiên từ cao đến thấp. Sau đó, chúng ta sử dụng hàm top() để lấy ra phần tử ưu tiên cao nhất trong hàng đợi và in ra màn hình. Tiếp theo, chúng ta sử dụng hàm pop() để xóa phần tử ưu tiên cao nhất và lại in ra phần tử ưu tiên cao nhất sau khi xóa.

Trong thực tế, priority queue có thể được sử dụng trong nhiều tình huống khác nhau, chẳng hạn như quản lý các tác vụ có ưu tiên trong lập trình, hoặc tìm kiếm đường đi ngắn nhất trong thuật toán tìm kiếm đường.

Ví dụ sử dụng priority queue c++

Ví dụ sau minh họa việc sử dụng priority queue để quản lý các tác vụ có ưu tiên:

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

struct Task {
    int priority;
    string name;
};

struct compare {
    bool operator()(Task t1, Task t2) {
        return t1.priority < t2.priority;
    }
};

int main()
{
    priority_queue<Task, vector<Task>, compare> pq;

    // them task vao hang doi uu tien
    pq.push({2, "Task 1"});
    pq.push({1, "Task 2"});
    pq.push({3, "Task 3"});
    pq.push({4, "Task 4"});

    // lay task uu tien cao nhat va xu ly
    while (!pq.empty()) {
        Task t = pq.top();
        cout << "Xu ly task: " << t.name << " co muc uu tien " << t.priority << endl;
        pq.pop();
    }

    return 0;
}

Trong ví dụ này, chúng ta đã tạo một priority queue cho các task với ưu tiên là một số nguyên. Chúng ta đã thêm vào 4 task với ưu tiên khác nhau vào hàng đợi. Sau đó, chúng ta sử dụng vòng lặp while để lấy ra task ưu tiên cao nhất từ hàng đợi và in ra thông tin của task đó và xử lý nó. Vòng lặp sẽ tiếp tục cho đến khi hàng đợi trống.

Trong ví dụ trên, chúng ta còn cần phải tạo một struct compare để so sánh ưu tiên của các task. Trong struct này chúng ta đã override operator() để so sánh hai task dựa trên ưu tiên của chúng.

Với ví dụ trên, chương trình sẽ in ra:

Copy codeXu ly task: Task 4 co muc uu tien 4
Xu ly task: Task 3 co muc uu tien 3
Xu ly task: Task 1 co muc uu tien 2
Xu ly task: Task 2 co muc uu tien 1

Với priority queue c++ chúng ta có thể sử dụng nó để quản lý các task có ưu tiên, tìm kiếm đường đi ngắn nhất trong thuật toán tìm kiếm đường, hoặc các tình huống khác mà cần sắp xếp các phần tử dựa trên ưu tiên của chúng.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now