目录
priority_queue的介绍
概念
特点
priority_queue的使用
基本操作
演示代码
编辑
priority_queue的模拟实现
仿函数
向上调整和向下调整
模拟实现的代码
priority_queue的介绍
概念
在C++标准库中，priority_queue是一个基于优先级堆的容器适配器。它的底层容器是vector，将其封装成堆来管理元素，确保元素按照特定的优先级顺序排列。
默认情况下，priority_queue是大堆，因为其的比较函数是std::less，如果想要建立小堆，则使用std::greater比较函数，这个比较函数其实是仿函数，接下来会提及。
特点
1.自动排序
元素根据优先级自动排序，最高优先级的元素总是在队列的前端。
2.只访问前端元素
只能访问队列的前端元素，即最高优先级的元素。
3.底层容器
使用vector作为底层容器来存储元素，但用户不能直接访问这个容器。
4.元素比较
priority_queue需要一个比较函数或函数对象来确定元素的优先级顺序，默认情况下使用std:less，即最大值优先。
priority_queue的使用
基本操作
empty()：检查队列是否为空。size()：返回队列中的元素数量。top()：访问队列前端的元素（不删除）。pop()：移除队列前端的元素。push()：向队列添加新元素。 演示代码
int main(){std::priority_queue<int, vector<int>, less<int>> pq;pq.push(2);pq.push(1);pq.push(4);pq.push(5);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;}
priority_queue的模拟实现
仿函数
要想实现priority_queue，我们首先需要了解仿函数。
在 C++ 中，仿函数（Functor）是一种重载了函数调用操作符 operator() 的类或结构体。仿函数可以像函数一样被调用，但它们实际上是对象，因此可以拥有成员变和成员函数。
仿函数是函数对象（function object）的一种，它们通常用于需要函数指针或函数引用的地方，尤其是当需要传递具有特定行为的对象时。
仿函数的一些关键特性：
重载 operator()：
operator()，使其能够像函数一样被调用。 状态存储：
仿函数可以拥有自己的数据成员，这些成员存储了仿函数的状态。行为封装：
仿函数可以封装特定的行为，这些行为可以通过其operator() 实现。 灵活性：
仿函数提供了比普通函数更多的灵活性，因为它们可以存储状态，并且可以被重载。STL 兼容性：
仿函数与 STL 容器和算法兼容，可以作为算法的参数传递。仿函数的简单示例
上面我们提到std::less就是一个仿函数，我们就来模拟实现下。
template<class T>class Less{public:bool operator()(const T& x, const T& y){return x < y;}};向上调整和向下调整
我们知道priority_queue其实是堆，既然是堆那就需要实现向上调整和向下调整算法。
void AdjustDown(int parent){int child = 2 * parent + 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[parent], _con[child]);parent = child;child = 2 * parent + 1;}else{break;}}}void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}模拟实现的代码
template<class T>class Less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public:void AdjustDown(int parent){int child = 2 * parent + 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[parent], _con[child]);parent = child;child = 2 * parent + 1;}else{break;}}}void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}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);}const T& top(){return _con[0];}bool empty() const{return _con.empty();}int size() const{return _con.size();}private:Container _con;Compare _com;};拜拜，下期再见?
摸鱼ing?✨?
