1. 什么是priority_queue

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

2. 構(gòu)造priority_queue

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

#include <queue>
priority_queue<int> pq;

默認(rèn)情況下，priority_queue是一個(gè)大頂堆，即隊(duì)首元素是最大的元素，由大到小排序。

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

具體語(yǔ)法：

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

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

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

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

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

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

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

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

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

3. priority_queue的常用操作

3.1 插入元素

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

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

3.2 訪問(wèn)隊(duì)首元素

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

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

3.3 刪除隊(duì)首元素

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

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

3.4 檢查隊(duì)列是否為空

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

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

3.5 獲取隊(duì)列大小

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

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

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

最新評(píng)論