C++ STL容器之priority_queue(優先隊列)快速入門

priority_queue稱為“優先隊列”，其底層是用堆實作。

在優先隊列中，隊首元素一定是目前隊列中優先級最高的哪一個。

例如，若在隊列中有如下元素且定義好了優先級：

埃羅芒阿（優先級3）
土間埋（優先級2）
公主殿下（優先級5）

複制

那麼出隊的序列為公主殿下（5）->埃羅芒阿（3）->土間埋（2）。

而且可以在任何時候往優先隊列裡面加入(push)元素，接着優先隊列底層的資料結構堆會随時調整結構，使得每次的隊首元素都是優先級最大的。（這裡的優先級是可以規定出來的，預設是數字越大優先級越大）

使用priority_queue需于代碼頭部添加

#include

，并且随後加上一句：

using namespace std;

即可。

priority_queue的定義

定義：

priority_queue name;

擷取堆頂元素

top()：可以獲得隊首元素（堆頂元素），時間複雜度為O(1)。

與隊列不一樣的是，優先隊列通過top()函數來通路隊首元素（堆頂元素）。（隊列是通過front()函數和back()函數通路下标）

入隊

push(x)：令x入隊，時間複雜度為O(logN)，其中N為目前優先隊列中的元素個數。

出隊

pop()：令隊首元素（堆頂元素）出隊，時間複雜度為O(logN)，其中N為目前優先隊列中的元素個數。

檢測是否為空

empty()：檢測優先隊列是否為空，傳回true為空，false為非空。時間複雜度為O（1）

擷取元素個數

size()：用來獲得優先隊列中元素的個數，時間複雜度為O(1)

代碼：

#include
#include
using namespace std;
int main(){
    priority_queue q;

    //入隊
    q.push(3);
    q.push(4);
    q.push(1);

    //通過下标通路元素
    printf("%d\n",q.top());//輸出4

    //出隊
    q.pop();
    printf("%d\n",q.top());//輸出3

    //檢測隊列是否為空
    if(q.empty() == true) {
        printf("Empty\n");
    } else {
        printf("Not Empty\n");
    }

    //擷取長度
    //printf("%d\n",q.size());//輸出3
}

複制

優先隊列内元素優先級的設定

常見用途

需要建立字元或字元串與整數之間映射的題目

判斷大整數或者其他類型資料是否存在的問題，可以把map當成bool數組用

字元串和字元串的映射也有可能會用到

延伸

（1)如果一個鍵需要對應多個值，隻能使用multimap而不能使用map。

（2）C++11标準還增加了unordered_map，以散列替代map内部的紅黑樹實作，使其可以用來處理值隻映射而不按key排序的需求，速度比map快很多。

優先隊列内元素優先級的設定

如何定義優先隊列内元素的優先級是運用好優先隊列的關鍵。

基本資料類型的優先級設定

一般情況下，數字大的優先級更高。（char類型的為字典序最大）

對于基本結構的優先級設定。下面兩種優先隊列的定義是等價的：

priority_queue<int> q;

priority_queue<int, vector<int>, greater<int>> q;

第二種定義方式中的括号裡：

第二個參數填寫的是成在底層資料結構堆(heap)的容器；

若第一個參數為double或char，則隻需要填寫
vector<double> 或 vector<char> 。
第三個參數是對一個參數的比較類； less<int> 表示數字大的優先級越大，而 greater<int> 則反之`

舉個例子：

如果想讓優先隊列總是把最小的元素放在隊首，需進行以下定義： priority_queue<int, vector<int>, grater<int>> q;

結構體的優先級設定

舉個例子：

下面是關于動漫人物的結構體

struct comic_character{ string name; int bust; };

現在希望按動漫人物胸圍大的為優先級高，就需要使用重載(overload)運算符小于"<"。

而重載是指對已有運算符進行重新定義，即把改變其功能将其重載為大于号的功能。

以下為其寫法：

struct comic_character{
    string name;
    int bust;
    friend bool operator < (comic_character c1, comic_character c2){
        return c1.bust < c2.bust;
    }
};

複制

其中，結構體中增加了一個函數。

"friend"為友元。

後面一大串是對comic_character類型的操作符“<”進行了重載。此處重載後小于号還是小于号的作用。

提示：重載大于号會編譯錯誤（一般來說隻需要重載小于号，即c1>c2等價于c2<c1，c1==c2等價于判斷 !(c1<c2)&&!(c2<c1) ）

若想要以胸圍小的動漫人物為優先級高，那麼隻需要把return中的小于改為大于号即可，此處不再贅述。

重大發現：重載與sort函數的比較。

這裡對小于号的重載與排序函數sort中cmp函數有點類似。它們的參數和函數内部看似都是一樣的。

雖然這兩者的作用是類似的，但是效果看上去似乎的“相反”的。

在sort中，如果是"return c1.bust > c2.price"，那麼則是按胸圍從大到小排序。

而在優先隊列的重載中卻是把胸圍小的放到隊首。

總之《優先隊列的重載與sort中的cmp函數的效果是相反的。

另外

怎麼把重載放在結構體外面（正如sort中的cmp函數）呢？

隻要把friend去掉，把小于号改成一對小括号，然後把重載的函數寫在結構體外面，同時将其struct包裝起來。

即：

struct comic_character{
    string name;
    int bust;
};
struct cmp{
    bool operator () (comic_character c1, comic_character c2){
        return c1.bust > c2.bust;
    }
};
int main(){
    priority_queue<comic_character, vector<comic_character>, cmp> q;
    ......
}

複制

小提示

（1）即使是基本資料類型或者其他STL容器（如set），也可通過“另外”部分的方式來定義優先級。

（小作業：想想怎麼定義？）

（2）使用top()函數前，必須使用empty()判斷優先隊列是否為空。

題外話

如果結構體内的資料較為龐大（如字元串或數組），建議使用引用來提高效率，在比較類的參數中加上"const"和"&"。

即:

在結構體内：

friend bool operator < (const comic_character &c1, const comic_character &c2){ return c1.bust > c2.bust; }

或

在結構體外：

bool operator () (const comic_character &c1, const comic_character &c2){ return c1.bust > c2.bust; }

常見用途

（1）可以解決一些貪心問題

（2）也可以對Dijkstra算法進行優化

優先隊列的本質是堆

本文标題：《C++ STL容器之priority_queue(優先隊列)快速入門》

本文連結：https://wnag.com.cn/816.html

特别聲明：除特别标注，本站文章均為原創，本站文章原則上禁止轉載，如确實要轉載，請電聯：[email protected]，尊重他人勞動成果，謝過~