Skip to content

[C++] STL 中的 priority_queue 優先權佇列筆記

Last Updated on 2022-02-19 by Clay

priority_queue（優先權佇列）是 C++ 標準模板函式庫（Standard Template Library, STL）中所提供的佇列容器，會優先返回優先權最高的元素。

在一般儲存 int 資料的情況下，元素的優先權由大到小排序，當然我們可以自行改變 priority_queue 的優先權定義。

priority_queue 使用方法筆記

以下是一個最簡單的範例程式：

  • push(): 將元素推入佇列
  • top(): 取出優先權最高的元素
  • pop(): 彈出（刪除）優先權最高的元素
#include <iostream>
#include <queue>
using namespace std;


int main() {
    // Init
    priority_queue<int> pq;
    pq.push(4);
    pq.push(9);
    pq.push(5);
    pq.push(1);
    pq.push(6);

    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }

    return 0;
}


Output:

9
6
5
4
1


可以看到，我們隨便推入佇列中的元素已經按照由大到小這樣的順序排序了；意味著越大的數值有著越高的優先權。


改變優先權

改成越小的數值的優先權越高

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


int main() {
    // Init
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(4);
    pq.push(9);
    pq.push(5);
    pq.push(1);
    pq.push(6);

    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }

    return 0;
}


Output:

1
4
5
6
9


這是最常見的改變之一，我們可以直接使用 greater<int> 來做到。


自定義優先權模式

如果我們希望偶數的優先權比奇數的大、且數字越小優先權越大，那麼我們可以用以下這樣的方法建構自己的優先權規則：

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


template <typename T>
class cmp {
    public: 
        bool operator()(T a, T b) {
            if (a % 2 == 1 && b % 2 == 0) {
                return true;
            }
            else if (a % 2 == 0 && b % 2 ==1) {
                return false;
            }
            else {
                return a > b;
            }
        }
};

int main() {
    // Init
    
    vector<int> v({1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
    priority_queue<int, vector<int>, cmp<int>> pq(v.begin(), v.end());

    while (!pq.empty()) {
        cout << pq.top() << endl;
        pq.pop();
    }

    return 0;
}


Output:

2
4
6
8
10
1
3
5
7
9


為了讓 demo 的效果比較清楚，我增加了一些數字，順便列出如何使用 vector<int> 容器來初始化 priority_queue<int>。

References

Read More

Tags:

Leave a Reply