合肥做网站哪家好,公司网站建设佛山哪家专业,百度客户端官网,中国企业排行榜优先级队列的基本使用
模拟实现上面的接口函数#xff0c;优先级队列不是队列#xff0c;而是类似一个堆一样的东西#xff0c;我们先来试试它的接口函数是怎么个样子的。 需要包含的头文件是queue。 #includeiostream
#includequeue
using namespace std;… 优先级队列的基本使用
模拟实现上面的接口函数优先级队列不是队列而是类似一个堆一样的东西我们先来试试它的接口函数是怎么个样子的。 需要包含的头文件是queue。 #includeiostream
#includequeue
using namespace std;
void priority_queuetest1()
{priority_queueint 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的升序。代码如下。 vectorint v { 6,5,4,3,2,1 };sort(v.begin(), v.end());for (auto e : v){cout e ;} 结果 1 2 3 4 5 6 如果要排降序的话就需要传一个参数就是仿函数过去。准确来说是对象而我们上面的优先级队列是类型编译器会自动去推算
使用如下
vectorint v { 6,5,4,3,2,1 };sort(v.begin(), v.end(),greaterint());for (auto e : v){cout e ;} 6 5 4 3 2 1 那如果我们要进行的是小堆呢就可以这样使用。
void priority_queuetest1()
{priority_queueint,vectorint,greaterint pq;pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout pq.top() ;pq.pop();}/*vectorint v { 6,5,4,3,2,1 };sort(v.begin(), v.end(),greaterint());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?spm1001.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;}}}
其他接口函数都是对我们的容器进行一个封装所以大体框架就是下面的这个
templateclass T,class Container vectorTclass 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_queueint pq;pq.push(5);pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout pq.top() ;pq.pop();}}
检查我们的代码的时候其实是可以先来看插入的逻辑的看看插入之后是不是建立成大堆如果建立堆问题出错了就只要两个地方会有问题一个就是我们插入逻辑插入逻辑一般不会有问题的可能再传参数的地方有问题还有就是我们的向上调整是不是存在一些逻辑问题。
重新认识仿函数
如何控制比较逻辑呢我们这里默认建立的是大堆我们需要通过仿函数来进行更改比较逻辑仿函数最大逻辑就是对象可以像函数那样进行比较。
快速实现仿函数。
templateclass Tstruct less{bool operator()(const T x, const T y){return x y;}};templateclass Tstruct greater{bool operator()(const T x, const T y){return x y;}};
因为是类我们可以传递模板参数。所以先来改变优先级队列的参数要在加上一个仿函数的类模板
所以我们只是需要在我们的函数里面定义一个对象。
templateclass Tstruct less{bool operator()(const T x, const T y){return x y;}};templateclass Tstruct greater{bool operator()(const T x, const T y){return x y;}};templateclass T,class Container vectorT,class Compare lessTclass 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_queueint 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
{templateclass Tstruct less{bool operator()(const T x, const T y){return x y;}};templateclass Tstruct greater{bool operator()(const T x, const T y){return x y;}};templateclass T,class Container vectorT,class Compare lessTclass 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_queueint,vectorint,greaterint 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_queueDate 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;}};
以上就是今天的分享我们下篇文章再见!!!
