👦個(gè)人主頁：@Weraphael
?🏻作者簡(jiǎn)介：目前學(xué)習(xí)C++和算法
??專欄：C++航路
🐋 希望大家多多支持，咱一起進(jìn)步！😁
如果文章對(duì)你有幫助的話
歡迎 評(píng)論💬 點(diǎn)贊👍🏻 收藏 📂 加關(guān)注?

---

一、priority_queue的介紹

• priority_queue是一個(gè)容器適配器，默認(rèn)使用vector作為其底層存儲(chǔ)數(shù)據(jù)的容器
• priority_queue在vector上使用了堆heap的算法將vector中元素構(gòu)造堆的結(jié)構(gòu)，因此，priority_queue就是堆。默認(rèn)情況下是大堆。（如何構(gòu)造成小堆在【仿函數(shù)】會(huì)講解到）

二、為什么priority_queue不像stack和queue一樣使用deque作為其底層存儲(chǔ)數(shù)據(jù)的容器呢

1. 這是因?yàn)?code>vector在插入和刪除元素時(shí)具有較好的性能表現(xiàn)。

在堆中插入新元素時(shí)，為了保持堆的特性（大堆/小堆）。則需要通過不斷地比較和移動(dòng)元素來完成。vector作為一個(gè)連續(xù)的內(nèi)存塊，可以更高效地進(jìn)行元素的插入操作。

相比之下，deque在插入和刪除操作時(shí)，需要考慮在數(shù)組的兩端進(jìn)行操作（頭部和尾部），并且要進(jìn)行元素的移動(dòng)操作，使得時(shí)間復(fù)雜度稍高于vector。

盡管deque在頭部和尾部插入/刪除操作上有一些優(yōu)勢(shì)，但對(duì)于優(yōu)先級(jí)隊(duì)列這種需要頻繁訪問和處理最高優(yōu)先級(jí)元素的場(chǎng)景來說，vector更加合適

2. 彈出pop元素：若要得到堆頂?shù)脑?#xff0c;需要將堆頂元素與最后一個(gè)元素交換，并重新調(diào)整堆使其滿足堆的性質(zhì)。同樣，由于vector是連續(xù)存儲(chǔ)的，這個(gè)操作也可以更高效地進(jìn)行。

3. deque的存儲(chǔ)空間不是連續(xù)的，因此在使用時(shí)需要更多的空間，可能會(huì)導(dǎo)致空間的浪費(fèi)。

三、priority_queue的常見操作

#include <iostream>
#include <queue>
using namespace std;// priority_queue的常見操作int main()
{// 默認(rèn)是大堆priority_queue<int> pq;pq.push(3);pq.push(5);pq.push(1);pq.push(4);pq.push(0);while (!pq.empty()){cout << pq.top() << ' ';pq.pop();}cout << endl;return 0;
}

【輸出結(jié)果】

注意：優(yōu)先級(jí)隊(duì)列也是不支持迭代器遍歷的！！！

四、模擬實(shí)現(xiàn)priority_queue

4.1 構(gòu)造函數(shù)

namespace wj
{template<class T, class container = vector<T>>class priority_queue{	private:void AdjustDown(int parent){// 建大堆// 找左右孩子大的size_t child = parent * 2 + 1;while (child < _con.size()){// 保證右孩子存在if (child + 1 < _con.size() && _con[child + 1] > _con[child]) {++child;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}public:// 無參默認(rèn)構(gòu)造priority_queue(){}// 帶區(qū)間的構(gòu)造template<class InputIterator>priority_queue(InputIterator first, InputIterator last){// 插入數(shù)據(jù)while (first != last){_con.push_back(*first);++first;}//  建堆操作 (默認(rèn)是大堆) for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}private:container _con;};
}

插入一個(gè)數(shù)據(jù)，由于還要保持大堆的性質(zhì)，如果尾插的結(jié)點(diǎn)要比其父結(jié)點(diǎn)大，就要進(jìn)行 向上調(diào)整

參考博客：點(diǎn)擊跳轉(zhuǎn)

4.2 刪除堆頂元素pop

void pop()
{// 頭尾結(jié)點(diǎn)交換,刪除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 然后再建堆AdjustDown(0);
}

4.3 插入push

void push(const T& val)
{// 尾部插入一個(gè)_con.push_back(val);// 再建堆AdjustUp(_con.size() - 1);
}

4.4 獲取堆頂元素top

const T& top()
{return _con[0];
}

4.5 判斷是否為空empty

bool empty()
{return _con.empty();
}

4.6 獲取個(gè)數(shù)大小size

size_t size()
{return  _con.size();
}

五、仿函數(shù)

5.1 什么是仿函數(shù)

• 仿函數(shù)（函數(shù)對(duì)象）是一種能夠被像函數(shù)一樣調(diào)用的對(duì)象。它通常是一個(gè)類或者結(jié)構(gòu)體，重載了函數(shù)調(diào)用運(yùn)算符 operator(),通過重載這個(gè)運(yùn)算符，我們可以將對(duì)象當(dāng)作函數(shù)來使用，實(shí)現(xiàn)了類似函數(shù)的行為。

• 仿函數(shù)可以有自己的狀態(tài)和成員變量，因此可以在多次調(diào)用中保持狀態(tài)。它可以接受參數(shù)，并返回一個(gè)值。

例如，定義一個(gè)加法仿函數(shù)可以這樣實(shí)現(xiàn)：

struct Add 
{int operator()(const int a, const int b) const {return a + b;}
};int main() 
{Add add;int result = add(3, 5);  // 調(diào)用仿函數(shù)cout << "add(3, 5) = " << result << endl;return 0;
}

在上面的例子中，Add是一個(gè)仿函數(shù)，它重載了函數(shù)調(diào)用運(yùn)算符 operator()，使得add對(duì)象可以像函數(shù)一樣被調(diào)用。通過add(3, 5)，我們可以得到結(jié)果8

• 在C++ 中，仿函數(shù)是一種靈活且強(qiáng)大的編程工具，常常用于算法和標(biāo)準(zhǔn)庫中的函數(shù)對(duì)象。

就比如說sort函數(shù)，默認(rèn)排的是升序

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int arr[] = { 5,1,4,2,0,3 };int arrSize = sizeof(arr) / sizeof(arr[0]);// less<int> 默認(rèn)可以不寫sort(arr, arr + arrSize, less<int>());for (int i = 0; i < arrSize; i++){cout << arr[i] << ' ';}cout << endl;return 0;
}

【輸出結(jié)果】

less是庫里提供的，其作用就是用于小于不等式比較的函數(shù)對(duì)象類

那么如果想排降序，可以將less替換成greater，這也是庫里提供的，其作用是用于大于不等式比較的函數(shù)對(duì)象類

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int arr[] = { 5,1,4,2,0,3 };int arrSize = sizeof(arr) / sizeof(arr[0]);// less<int> 默認(rèn)可以不寫sort(arr, arr + arrSize, greater<int>());for (int i = 0; i < arrSize; i++){cout << arr[i] << ' ';}cout << endl;return 0;
}

【輸出結(jié)果】

5.2 實(shí)現(xiàn)priority_queue的仿函數(shù)

namespace wj
{template<class T, class container = vector<T>, class Compare = less<T>>class priority_queue{private:void AdjustDown(int parent){Compare com;// 建大堆// 找左右孩子大的size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) // 保證右孩子存在{++child;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}public:// 無參默認(rèn)構(gòu)造priority_queue(){}// 帶區(qū)間的構(gòu)造template<class InputIterator>priority_queue(InputIterator first, InputIterator last){// 插入數(shù)據(jù)while (first != last){_con.push_back(*first);++first;}//  建堆操作 (默認(rèn)是大堆) for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void pop(){// 頭尾結(jié)點(diǎn)交換,刪除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 然后再建堆AdjustDown(0);}void push(const T& val){// 尾部插入一個(gè)_con.push_back(val);// 再建堆AdjustUp(_con.size() - 1);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return  _con.size();}private:container _con;};
}

注意：如果在priority_queue中放自定義類型的數(shù)據(jù)，用戶需要在自定義類型中提供>或者<的重載。

namespace wj
{template<class T, class container = vector<T>, class Compare = less<T>>class priority_queue{private:void AdjustDown(int parent){Compare com;// 建大堆// 找左右孩子大的size_t child = parent * 2 + 1;while (child < _con.size()){// 改動(dòng)if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) // 保證右孩子存在{++child;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}public:// 無參默認(rèn)構(gòu)造priority_queue(){}// 帶區(qū)間的構(gòu)造template<class InputIterator>priority_queue(InputIterator first, InputIterator last){// 插入數(shù)據(jù)while (first != last){_con.push_back(*first);++first;}//  建堆操作 (默認(rèn)是大堆) for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void pop(){// 頭尾結(jié)點(diǎn)交換,刪除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 然后再建堆AdjustDown(0);}void push(const T& val){// 尾部插入一個(gè)_con.push_back(val);// 再建堆AdjustUp(_con.size() - 1);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return  _con.size();}private:container _con;};// 日期類class Date{public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
}