目錄
- 一、priority_queue介紹
- 二、priority_queue使用
- 三、模擬實作
- 四、完整代碼
一、priority_queue介紹
👉 cplusplus官網 : priority_queue的說明
優先級佇列和普通的佇列不是一個概念，普通的queue遵守先進先出的規則，而優先級佇列遵守優先級最高的先出，本質上就是堆排
二、priority_queue使用
我們給上一組資料，呼叫top函式進行列印輸出發現最大值優先輸出，默認降序
如果要排成升序呢？
官網提供了模版引數，我們發現這里傳的不是型別而是物件，如果要排升序通過傳greater，默認是less
三、模擬實作
我們在實作前需要注意，模版是不支持分離編譯的，因此我們在hpp里面進行宣告和定義
首先默認創建一個大堆，這里就不再贅述概念，可以參考下面的鏈接
👉 堆排詳細說明
//大堆
template<class T, class Container = vector<T>, class Compare = Less<T> >
class priority_queue{
public:
void push(const T& x){
_con.push_back(x);
AdjustUp(_con.size() - 1); //向上調整保持大堆狀態
}
void pop(){
swap(_con[0], _con[_con.size()-1]); //頭尾交換，向下調整
_con.pop_back();
AdjustDown(0);
}
private:
Container _con;
}
下面是向上和向下調整函式實作，注意默認的是Less類模版
void AdjustUp(size_t child){
size_t parent = (child-1)/2;
while(child > 0){
if(_con[child] > _con[parent]){
swap((_con[child] > _con[parent]);
child = parent;
parent = (child-1)/2;
}else{
break;
}
}
}
void AdjustDown(size_t parent){
int child = parent*2 + 1;
while(child < _con.size()){
if(child < _con.size() && _con[child] < _con[child+1] ){
child++;
}
if(_con[parent] < _con[child]){
swap(_con[parent], _con[child] );
parent = child;
child = parent * 2 + 1;
}else{
break;
}
}
}
這里在建構式的時候就需要建堆了
//默認構造,不用寫什么，會自動呼叫建構式
priority_queue(){}
//帶參構造
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last){
//資料插入
while(first != last){
_con.push_back(*first);
++first;
}
//建堆
for(int i= (_con.size()-1-1) / 2 ; i >= 0; --i){ // size()-1 是最后一個資料的下標，父親的話再-1 ，除2
AdjustDown(i);
}
}
最后我們考慮一個問題：
解決完大堆的實作后，如果在不修改符號的情況下變小堆呢？
所以就有了仿函式的概念
//仿函式/函式物件，可以像函式一樣去使用
//建大堆，排升序
class Less{
public:
bool operator()(const T& x, const T& y){
return x < y;
}
};
//建小堆，排降序
template<class T>
class Greater{
public:
bool operator()(const T& x, const T& y){
return x > y;
}
};
四、完整代碼
Gitee鏈接🔗 🔗 🔗
👉 👉 👉 priority_queue simulation 👈 👈 👈
創作不易，如果文章對你幫助的話，點贊三連哦:)
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/377148.html
標籤：其他
上一篇：C++堆記憶體錯誤：CRT detected that the application wrote to memory before start of heap buffer