【C++】优先级队列宝藏岛

 
> 🍃 本系列为初阶C++的内容，如果感兴趣，欢迎订阅🚩
> 🎊个人主页:[小编的个人主页])小编的个人主页
>  🎀   🎉欢迎大家点赞👍收藏⭐文章
> ✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

---

目录

 🐼前言 

  🐼priority_queue的介绍和使用

 🐼仿函数

🐼priority_queue的模拟实现

 🐼总结

---

 🐼前言 

🌈 在上一节，我们通过适配器模式，实现了一种高效、灵活且易于扩展的方式来实现栈和队列，通过适配器转换出我们想要的类，让原本互不相容的两个接口能够协同工作。本篇文章将继续采用适配器这种设计方式，带你认识优先级队列的使用场景，完成优先级队列(priority_queue)的实现。

🌻如果你还不了解适配器，可以看这一节: stack和queue的适配器模式

🌻如果你还不了解堆，可以看这一节:堆-上和 堆-下

  🐼priority_queue的介绍和使用

priority_queue的介绍:

🔍使用场景

优先级队列在我们日常生活中也有很多使用场景,比如在医院的急诊室😷中，患者不是按照到达时间先后顺序接受治疗，而是根据病情的严重程度（优先级）进行排序。病情最严重的患者会被优先处理，即使他们不是最早到达的。又或是在餐厅中，顾客的订单可能根据订单的复杂程度或紧急程度进行优先处理。例如，简单的订单（如一杯咖啡😋）可能会比复杂的订单（如一份牛排）更早完成，即使它们不是最早下单的。这种优先级排序的机制类似于 priority_queue

🔍C++中:优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中优先级最高。我们在容器中可以随时插入元素，它通过动态调整队列顺序，确保优先级最高的元素始终位于队列顶部。

我们下面看一下优先级队列类的类模版参数:

我们可以看到优先级队列有三个模版参数，分别是类型，适配器(缺省参数默认是<vector>),以及仿函数。默认是大堆

我们再看其常见接口:

🔍 priority_queue的使用:

首先，优先级队列并不是队列，底层可以采用堆结构的一种强大的容器。优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，所有需要用到堆的位置，都可以考虑使priority_queue。注意：默认情况下priority_queue是大堆。

比如:我们采用优先级队列来建堆并访问堆顶元素:

#include<iostream>
#include <vector>
#include <queue>using namespace std;void TestPriorityQueue()
{// 默认情况下，创建的是大堆，其底层按照小于号比较vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };priority_queue<int> q1;for (auto& e : v)q1.push(e);cout << q1.top() << endl;// 如果要创建小堆，将第三个模板参数换成greater比较方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;
}

⭐️我们也可以拿自定义类型进行建堆，只要我们提供了自定义类型的比较(自定义类型的比较可以通过运算符重载).

比如以日期类的大小关系来建堆:

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)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}private:int _year;int _month;int _day;};void TestPriorityQueue(){// 大堆，需要用户在自定义类型中提供<的重载priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;// 如果要创建小堆，需要用户提供>的重载priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout << q2.top() << endl;}

🍁想必看到这里，小伙伴们对优先级队列有了充分的认识。它不就是堆嘛❓❓❓😶其实，priority_queue是堆的具体体现，是一个封装了堆操作的高级工具，而堆是实现这种功能的底层结构。priority_queue是一个更高级的数据结构，封装了堆的操作，提供了更简洁的接口😏。

🐝打个比喻:堆像是一个“有序的箱子”，里面的物品（元素）按照一定的规则（堆序）排列，需要手动调整物品的位置。

priority_queue则像是一个“自动排序的传送带”，你只需要把物品放上去（push），它会自动按照优先级排序，并且总是让你先拿到最重要的物品（top 和 pop）。

 🐼仿函数

🍁在实现优先级队列之前，我们先简单认识一下仿函数，后续我们在学习。在 C++ 中， 仿函数（Functor） 是一种特殊的函数对象，它通过 重载operator() ，使得对象可以像函数一样被调用。仿函数本质上是一个类，但它的行为类似于函数。比如:用仿函数来实现加法逻辑:

class Adder {
public:int operator()(int a, int b) const {return a + b;}
};int main() {Adder add;int result = add(3, 4);  // 使用仿函数对象调用std::cout << result << std::endl; return 0;
}

📆通过类Adder中重载operator(),add看上去好像是函数调用一样，像一个披着函数外衣的对象。

通过这种方式，对象可以像普通函数一样被调用，但同时可以利用类的其他特性（如成员变量、继承等）。通过重载operator()实现的函数对象，它结合了类的灵活性和函数的简洁性。仿函数广泛应用于 C++ STL 中，用于自定义算法的行为。 

🐼priority_queue的模拟实现

 基于堆的思想，我们先简单实现一个能完成大堆的priority_queue

namespace lsg
{template<class T, class Container = vector<T>>class priority_queue{public:void push(const T& x){_con.push_back(x);Adjustup(size() - 1);}void pop(){std::swap(_con[0], _con.back());_con.pop_back();Adjustdown(0);}bool empty(){return _con.empty();}const T& top() const{return _con[0];}size_t size() const{return _con.size();}private:void Adjustup(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_con[parent]< _con[child]) //相当于调用com.opeartor(x,y){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void Adjustdown(size_t parent){size_t child = parent * 2 + 1;while (child < size()){//大堆找较大的孩子if (child + 1 < size() && _con[child]< _con[child + 1]){child++;}if (_con[parent]<_con[child]){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}Container _con;};
}

✅代码解析:

🏃我们这里priority_queue的底层结构就是堆，因此此处只需对堆进行通用的封装即可，堆结构底层是<vector>加以限制，因此可以借助<vector>作为适配器。基于向上调整算法和向下调整算法，让优先级队列永远保持优先级最高的在堆顶。

👆向上调整算法:对于刚刚插入一个小伙伴，它不知道在这个队伍中的"重要程度"，因此，它要不断向上查找，直到找到合适自已的位置。

👇向下调整算法:对于把最后一个元素交换到优先级最高位置(第一个位置)的小伙伴，他要不断向下比较，和比自已"重要程度"高的人交换位置，直到找到合适自已的位置。具体操作:先交换堆顶元素与堆中最后一个元素，然后删去最后一个位置的元素，最后向下调整保持堆结构。

👏细节:这里向上调整算法和向下调整算法只供类中成员函数使用，外界无需使用，我们可以封装成(private)权限😃

💅如果我们再实现一个小堆逻辑的priority_queue，只需要更换一下比较逻辑。如果我们再重新写一个小堆逻辑的priority_queue，显得有点繁琐了。在上面我们介绍了仿函数，仿函数就是来用于和容器结合，实现逻辑变换的。而我们这里恰好需要一个相反的大于&&小于逻辑，于是我们这里就可以利用仿函数来控制比较逻辑😃， 定义元素之间的比较逻辑，从而灵活地改变优先队列的行为。

C++标准库中<less>类对象默认是大堆逻辑

namespace lsg
{template<class T>struct less{bool operator()(const T& x,const T& y){return x < y;}};template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;}};template<class T,class Container = vector<T>,class Compare  = less<T>>//less建大堆class priority_queue{public:void push(const T& x){_con.push_back(x);Adjustup(size()-1);}void pop(){std::swap(_con[0], _con.back());_con.pop_back();Adjustdown(0);}bool empty(){return _con.empty();}const T& top() const{return _con[0];}size_t size() const{return _con.size();}private:void Adjustup(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent],_con[child])) //相当于调用com.opeartor(x,y){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void Adjustdown(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child<size()) {//大堆找较大的孩子if (child + 1 < size() &&  com(_con[child] , _con[child + 1])){child++;}if (com(_con[parent] , _con[child])){std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}Container _con;};
}

通过自定义比较逻辑，我们可以轻松地实现小堆或大堆，而无需重新编写底层逻辑😁。

 🐼总结

 优先级队列就像一个“魔法盒”🎃，当一个个元素进去，它总是会给这些元素的重要程度排个序，优先级最高的往往占据首位，优先级最低的只能乖乖让位置。通过仿函数，它就像一个"智能控制管家"，让我们控制了这个"比较规则"，就好比，如果刚开始身高最高的人优先级最高，通过仿函数的控制，我们也可以让最矮的人优先级最高😜。

  感谢你耐心地阅读到这里，你的支持是我不断前行的最大动力。如果你觉得这篇文章对你有所启发，哪怕只是一点点，那就请不吝点赞👍，收藏⭐️，关注🚩吧！你的每一个点赞都是对我最大的鼓励，每一次收藏都是对我努力的认可，每一次关注都是对我持续创作的鞭策。希望我的文字能为你带来更多的价值，也希望我们能在这个充满知识与灵感的旅程中，共同成长，一起进步。再次感谢你的陪伴，期待与你在未来的文章中再次相遇！⛅️🌈 ☀️