C++優(yōu)先級隊列的使用指南與模擬實現
一、priority_queue的介紹
優(yōu)先級隊列是一種容器適配器，根據嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的。
此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素（優(yōu)先級隊列中位于頂部的元素）。
優(yōu)先級隊列被實現為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue 提供一組特定的成員函數來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優(yōu)先級隊列的頂部。
底層容器可以是任何標準容器類模板，也可以是其他特定設計的容器類。容器應該可以通過隨機訪問、迭代器訪問，并支持以下操作：
empty()：檢測容器是否為空
size()：返回容器中有效元素的個數
front()：返回容器中第一個元素的引用
push_back()：在容器尾部插入元素
pop_back()：刪除容器尾部元素
標準容器類 vector 和 deque 滿足這些需求。默認情況下，如果沒有為特定的 priority_queue 類實例化指定容器類，則使用 vector。
需要支持隨機訪問迭代器，以便始終在內部保持堆結構。容器適配器通過在需要時自動調用算法函數 make_heap、push_heap 和 pop_heap 來自動完成次操作。
二、priority_queue的使用
優(yōu)先級隊列默認使用 vector 作為其底層存儲數據的容器，在 vector 上又使用了堆算法將 vector 中元素構造成堆的結構，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考慮使用 priority_queue。注意：默認情況下 priority_queue 是大堆。
| 函數聲明 | 接口說明 |
|---|---|
| priority_queue() | 構造一個空的優(yōu)先級隊列 |
| empty() | 檢測優(yōu)先級隊列是否為空，是返回 true，否則返回 false |
| top() | 返回優(yōu)先級隊列中最大（最?。┰?，即堆頂元素 |
| push(x) | 在優(yōu)先級隊列中插入元素 x |
| pop() | 刪除優(yōu)先級隊列中最大（最下）元素，即堆頂元素 |
小Tips：默認情況下，priority_queue 是大堆（默認第三個模板參數是 less）；如果在 priority_queue 中放自定義類型的數據，用戶需要在自定義類型中提供 > 或者 < 的重載。
2.1 數組中的第k個最大元素
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
//建一個大堆，向下調整建堆的時間復雜度是O（N）
priority_queue<int> pq(nums.begin(), nums.end());
//pop k-1次,時間復雜度是O(K*logN)
while(--k)
{
pq.pop();
}
return pq.top();
}
};上面這種做法當 K 的值接近 N 的時候，它的時間復雜度就是 O(N*logN)，是不滿足題目要求的，下面再用另外一種方法來解決。
lass Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
//用前k個數建一個小堆
priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
//遍歷剩下的 N-k 個，比堆頂大就換進去
//時間復雜度是 (N-K)logN
for(size_t i = k; i < nums.size(); i++)
{
if(nums[i] > pq.top())
{
pq.pop();
pq.push(nums[i]);
}
}
return pq.top();
}
};上面這種解法是先用數組中的前 K 個元素建一個小堆，然后從數組的第 K+1 個元素開始往后遍歷，遇到比堆頂元素大的就將堆頂的元素 pop 出來，將當前元素 push 進去。建堆的時間復雜度是 O(K)，更新小堆的時間復雜度是 O((N-K)logK)，這種做法當 K 很小的時候時間復雜度可以近似看做 O(NlogK)，當 K 很大的時候，時間復雜度可以近似看做 O(logK)。
三、priority_queue模擬實現
3.1 仿函數
仿函數本質上一個類，之所以把它叫仿函數是因為這個類的對象可以像函數一樣去使用。舉例如下：
//一個仿函數
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
int main()
{
Less<int> lessfunc;//定義一個對象
cout << lessfunc(1, 2) << endl;//該類型對象可以像函數一樣去使用
//cout << lessfunc.operator()(1, 2) << endl;//和上面等價
return 0;
}小Tips：仿函數一般都是類模板，這樣就可以支持不同類型的大小比較，前提是該種類型重載實現了比較運算符。仿函數的誕生是為了代替函數指針，函數指針的可讀性比較差。
3.2 成員變量
template<class T, class Container=std::vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
//成員
private:
Container _con;
};小Tips：需要注意這里有三個模板參數，第一個模板參數表示要在優(yōu)先級隊列中存儲的數據類型；優(yōu)先級隊列本質上也是一個容器適配器，所以第二個模板參數表示優(yōu)先級隊列要使用的底層容器；第三個模板參數是一個仿函數，用來進行大小比較的，因為優(yōu)先級隊列中會涉及到建大堆還是建小堆，中間會涉及到比較，如果沒有這個仿函數，那么大小比較就只能寫死了，這樣不太好。
3.3 成員函數
3.3.1 構造函數
priority_queue()
{}
template<class InputeIterator>
priority_queue(InputeIterator first, InputeIterator last)
{
//先將數據插入
while (first != last)
{
_con.push_back(*first);
++first;
}
//建堆,從最后一個非葉子節(jié)點開始向下調整
for (int i = (_con.size() - 1) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}小Tips：迭代器區(qū)間構造函數是一個函數模板，只要是能支持 ++ 操作的迭代器區(qū)間都可以，即單向迭代器、雙向迭代器、隨機迭代都可以。其次將數據插入容器后還需要建堆，這里采用向下調整建堆，它的時間復雜度是 O(N)。
3.3.2 AdjustDown
void AdjustDown(int parent)
{
Compare com;
while (parent * 2 + 1 < (int)_con.size())
{
//找到最大的孩子
int maxchild = parent * 2 + 1;
if (maxchild + 1 < (int)_con.size() && com(_con[maxchild], _con[maxchild + 1]))
{
maxchild++;
}
//和父節(jié)點比較
if (com(_con[parent], _con[maxchild]))
{
std::swap(_con[maxchild], _con[parent]);
parent = maxchild;
}
else
{
break;
}
}
}小Tips：在仿函數的加持下，向下調整代碼中的大小比較不再固定，建大堆和小堆這一份代碼就夠了，最終是大堆還是小堆是由仿函數來控制的。
3.3.3 push
void push(const T& val)
{
_con.push_back(val);
AdjustUp(_con.size() - 1);
}小Tips：在優(yōu)先級隊列的尾部追加數據，會涉及到向上調整，向上調整的代碼如下所示。
3.3.4 AdjustUp
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)//父親不會小于0，因此這里的判斷條件要用孩子大于0，孩子等于0說明已經調整到根節(jié)點，就無需繼續(xù)調整了
{
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;//這里parent不會小于0
}
else
{
break;
}
}
}3.3.5 pop
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}小Tips：優(yōu)先級隊列中出數據，出的是堆頂的數據，堆頂的數據也就是容器中的第一個數據，如果底層容器是 vector 那么堆頂的數據就是下標為 0 的數據，出堆頂的數據不能直接使用頭刪，這樣會導致后面數據的父子關系全亂了。正確的做法是，將堆頂的數據和容器中的最后一個數據交換，然后執(zhí)行 pop_back 去刪除，最后還需要從根節(jié)點開始執(zhí)行一次向下調整，讓交換到堆頂的數據去到它應該去的地方。
3.3.6 empty
bool empty()
{
return _con.size() == 0;
}3.3.7 size
size_t size()
{
return _con.size();
}以上就是C++優(yōu)先級隊列的使用指南與模擬實現的詳細內容，更多關于C++優(yōu)先級隊列的資料請關注腳本之家其它相關文章！
相關文章
本篇文章是對c++中inline的用法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
c語言for、while和do-while循環(huán)之間的區(qū)別
大家好，本篇文章主要講的是c語言for、while和do-while循環(huán)之間的區(qū)別，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
學習了c++有一周有余了吧,感謝孫鑫老師的視頻教程,讓我 對C++有了基本的了解,并理解到C++與.net 的許許多多的區(qū)別,更要感謝網民為programaking的人,會為我提供了超級瑪麗制作揭秘 這套寶貴的教程,讓我 做做出了這個項目,對c++ 有了一個更深層次的認識2012-11-11
當年學習C語言的第一門課就提到過標記(Token)的概念，不過，相信在多年之后你再次聽到這個術語時會一臉懵逼，比如我。因此特地翻了翻資料，整理下來這些筆記，希望對大家有所幫助2022-11-11
這篇文章主要介紹了關于c++11與c風格路徑拼接的速度對比分析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
如果從事過C++?Windows客戶端開發(fā)，大家對MFC、Qt、DuiLib等各種DirectUI應該有了解，本篇給大家介紹一個超級輕量級的C++開源跨平臺圖形界面框架ImGUI，感興趣的可以了解一下2021-11-11
這篇文章主要介紹了C++ template用法案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-09-09
這篇文章主要為大家詳細介紹了OpenCV實現圖像角點檢測，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要為大家詳細介紹了利用C語言結構體實現通訊錄，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要介紹了VC定時器的用法,以實例形式詳細講述了VC定時器的原理與具體用法,非常具有實用價值,需要的朋友可以參考下2014-10-10