1. 什么是priority_queue

priority_queue是C++中的容器，實現(xiàn)優(yōu)先隊列。由于底層采用堆實現(xiàn)，所以插入和刪除操作的時間復雜度為O(logn)，查找隊首元素的時間復雜度為O(1)。

2. 構造priority_queue

【1】使用priority_queue需要先包含頭文件<queue>。以下是priority_queue的基本語法：

#include <queue>
priority_queue<int> pq;

默認情況下，priority_queue是一個大頂堆，即隊首元素是最大的元素，由大到小排序。

【2】如果是自定義比較，比如比較從小到大比較或不壞類中的某個元素，則在聲明priority_queue對象時，需要指定元素類型和比較函數(shù)。

具體語法：

// 聲明一個元素類型為T，比較函數(shù)為Compare的priority_queue對象
priority_queue<T, vector<T>, Compare> pq;

其中，T為元素類型，std::vector<T>為底層容器類型，Compare為元素的比較函數(shù)，是函數(shù)對象。

例如若要聲明一個整型優(yōu)先隊列，要求從小到大排序，可以這樣寫：

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

例如若要聲明一個字符串優(yōu)先隊列，要求按照字符串大小從小到大排序，可以這樣寫：

// 自定義比較函數(shù)
struct cmp {
    bool operator() (const std::string& s1, const std::string& s2) {
        return s1.size() > s2.size();  // 按字符串長度從小到大排序
    }
};

priority_queue<string, vector<string>, cmp> pq;

【3】用已有的優(yōu)先隊列賦值

priority_queue<int> pq(vec.begin(), vec.end()); // 創(chuàng)建一個包含vec中所有元素的優(yōu)先隊列

3. priority_queue的常用操作

3.1 插入元素

使用成員函數(shù)push()可以向priority_queue中插入一個元素，插入后會自動按照優(yōu)先級調(diào)整元素位置。

pq.push(10); // 向隊列中插入元素10 pq.push(20); // 向隊列中插入元素20

3.2 訪問隊首元素

使用成員函數(shù)top()可以訪問priority_queue中的隊首元素，即最大（?。┲怠?/p>

int max_element = pq.top(); // 獲取大頂堆的隊首元素，即最大值

3.3 刪除隊首元素

使用成員函數(shù)pop()可以刪除priority_queue中的隊首元素，即最大（?。┲?。

pq.pop(); // 刪除大頂堆的隊首元素，即最大值

3.4 檢查隊列是否為空

使用成員函數(shù)empty()可以檢查priority_queue是否為空。

if (pq.empty()) { 
    // 隊列為空 
}

3.5 獲取隊列大小

使用成員函數(shù)size()可以獲取priority_queue中元素的個數(shù)。

int count = pq.size(); // 獲取隊列中元素的個數(shù)

到此這篇關于C++優(yōu)先隊列的使用小結的文章就介紹到這了,更多相關C++優(yōu)先隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！ 

最新評論