优先级队列

 优先级队列的基本使用

模拟实现上面的接口函数，优先级队列不是队列，而是类似一个堆一样的东西，我们先来试试它的接口函数是怎么个样子的。

 需要包含的头文件是queue。

 

#include<iostream>
#include<queue>
using namespace std;
void priority_queuetest1()
{priority_queue<int> pq;pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}}
int main()
{priority_queuetest1();return 0;
}

这就是我们的基本使用方法，但是我们运行我们的代码之后发现的打印结果不是升序的

打印结果· ： 4 3 2 1

这里就要说明一个问题，我们建立的堆是大堆，也就导致了最后的打印结果就是降序，这个地方会出现一个叫仿函数的东西，我们在后面进行模拟实现的时候回来看到这个。

需要记住小于是大堆，大于是小堆！！！！（后面会解释）

我们的sort排序也是这个样子的。

如果我们用sort对我们的排序要进行排序的时候，默认是升序，原因就是我们进行传仿函数的时候传的是less，我们可以来看看sort的文档。

 

这里我们传的就是一个对象，而上面的优先级队列传的不是对象，而是模板参数，这里需要注意一下，我们假如要排一个 vector的升序。代码如下。

	vector<int> v = { 6,5,4,3,2,1 };sort(v.begin(), v.end());for (auto e : v){cout << e << " ";}

结果 ： 1 2 3 4 5 6

如果要排降序的话就需要传一个参数就是仿函数过去。准确来说是对象，而我们上面的优先级队列是类型，编译器会自动去推算！！！！

使用如下

vector<int> v = { 6,5,4,3,2,1 };sort(v.begin(), v.end(),greater<int>());for (auto e : v){cout << e << " ";}

 6  5  4  3  2  1

 那如果我们要进行的是小堆呢，就可以这样使用。

void priority_queuetest1()
{priority_queue<int,vector<int>,greater<int>> pq;pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}/*vector<int> v = { 6,5,4,3,2,1 };sort(v.begin(), v.end(),greater<int>());for (auto e : v){cout << e << " ";}*/}

这里C语言和C++的区别 ，C语言是没有仿函数的，他是用函数指针来进行调用的。比如qsort函数就是这样的。

仿函数

1 ：仿函数其实就是一个类，只要我们在类里面重载了运算符括号，这个类我们就可以认定为具有仿函数功能！

2 ： 它的对象可以像函数一样去调用。

3 ： 写成模板的时候，那么我们任意数据都可以来进行使用。

那如果我们要写一个最基本的仿函数是怎么个样子，首先就是它得是一个类，是不是要写成模板，取决于你自己。

void priority_queuetest2()
{struct Less//区别于库里面{bool operator()(const int& x, const int& y){return x < y;}};Less com;cout << Less()(1, 2) << endl;cout << com(5, 2) << endl;cout << com.operator()(3,1) << endl;
}

 模拟实现队列

我们先实现一个不加上仿函数的优先级队列，根据文档里的接口先来实现一些push， 我们的堆是怎么进行push的呢？？

因为我们的堆其实就是一个满二叉树的结构，那在数组里其实就是尾插进去一个数，但是尾插进去之后，可能就不是满二叉树了，所以要做的就是向上调整。

优先级队列的插入push

void push(const T& val){_con.push_back(val);adjust_up(_con.size() - 1);}

push的之后就需要进行向上调整，在这里我们是用了其他容器来进行实现的，因为二叉树是共和数组，所以这里的默认容器就是vector。

需要进行的是向上调整，在我的文章堆里面是讲过这个的，大家可以跳转到下面的这个链接当中

https://blog.csdn.net/2301_76895050/article/details/134611394?spm=1001.2014.3001.5501

向上调整

void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

还有就是pop，我们需要注意的是pop不是pop尾部的数据，而是数组下标是0位置二的，我们只需要先交换头和尾位置的数据，然后再进行删除，这个时候把头部的数据删掉了，但是却不是二叉树，这个时候（默认是大堆）堆顶的数据不是最大的，所以需要做的就是向下进行调整。

优先级队列的pop

void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}

向下调整

void adjust_down(size_t parent){size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){child++;}if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}

其他接口函数都是对我们的容器进行一个封装，所以大体框架就是下面的这个

template<class T,class Container = vector<T>>class priority_queue{public://默认是大堆void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){child++;}if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(const T& val){_con.push_back(val);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}T top(){return _con[0];}private:Container _con;};

写完一个代码就需要进行测试一下，我们可以插入一下数据，看看是不是大堆，然后打印我们的数据，来看看是不是有序的就行了、

测试代码

void priority_queuetest1(){priority_queue<int> pq;pq.push(5);pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}}

检查我们的代码的时候其实是可以先来看插入的逻辑的，看看插入之后是不是建立成大堆，如果建立堆问题出错了，就只要两个地方会有问题，一个就是我们插入逻辑，插入逻辑一般不会有问题的，可能再传参数的地方有问题，还有就是我们的向上调整是不是存在一些逻辑问题。

重新认识仿函数

如何控制比较逻辑呢，我们这里默认建立的是大堆，我们需要通过仿函数来进行更改比较逻辑，仿函数最大逻辑就是，对象可以像函数那样进行比较。

快速实现仿函数。

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>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>>class priority_queue{public://默认是大堆void adjust_up(size_t child){Compare com;size_t 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;}}}void adjust_down(size_t parent){Compare com;size_t 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[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(const T& val){_con.push_back(val);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}T top(){return _con[0];}private:Container _con;};void priority_queuetest1(){priority_queue<int> pq;pq.push(5);pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}}

优势1 ： 只要更改仿函数就能更改我们的比较逻辑 大堆也就变成小堆

优势2 ： 是一个类，理解起来和写起来都比较方便，c语言要实现这样只能通过函数指针，函数指针是个比较麻烦的东西

完整代码

namespace tjl
{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>>class priority_queue{public://默认是大堆void adjust_up(size_t child){Compare com;size_t 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;}}}void adjust_down(size_t parent){Compare com;size_t 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[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(const T& val){_con.push_back(val);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}T top(){return _con[0];}private:Container _con;};void priority_queuetest1(){priority_queue<int,vector<int>,greater<int>> pq;pq.push(5);pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}}
}

 补充

仿函数的作用可不只是这样嗷，我们如果要来比较一下我们的日期应该是怎么来实现呢。

	class Date{public:friend ostream& operator<<(ostream& _cout, const Date& d);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);}private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}

这个时候因为我们假设比较Date，当然我们日期也可以使用之前的方式来进行比较，这是这个时候的比较类型是自定义的。

代码如下

 

void priority_queuetest2(){priority_queue<Date> pq;pq.push({2023,1,3});pq.push({2013,1,7});pq.push({2034,3,1});while (!pq.empty()){cout << pq.top() << " ";pq.pop();}}

但是如果我们现在要进行的是Date*的比较呢，这个时候就不可了，首先比较的时候重载必须是自定义的类型，内置类型是不能进行重载的，比较逻辑就是不正确的，所以这个时候要在写一个仿函数

class GreaterPDate{public:bool operator()(const Date* p1, const Date* p2){return *p1 > *p2;}};

以上就是今天的分享，我们下篇文章再见!!!