如何建设自己的企业网站,网络规划设计师希赛,沧州网站群,企业网站建设前期准备文章目录一、priority_queue类简介二、priority_queue类常用接口三、priority_queue类的使用四、STL中priority_queue类的模拟实现一、priority_queue类简介
优先队列是一种容器适配器#xff0c;根据严格的弱排序标准#xff0c;它的第一个元素总是它所包含的元素中最大的。…
文章目录一、priority_queue类简介二、priority_queue类常用接口三、priority_queue类的使用四、STL中priority_queue类的模拟实现一、priority_queue类简介
优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作empty() 检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素。标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。 以上内容来自www.cplusplus.com priority_queue类文档的介绍在STL的学习中推荐大家看这个文档对每个类都有详细的介绍。 总结 优先级队列 (priority_queue) 属于STL中的容器适配器其底层存储数据的容器默认使用vector并且使用堆算法使得vector中的元素构造成堆的结构。所以可以说优先级队列 (priority_queue) 就是堆默认情况下是大堆。在使用时与queue相同要引入头文件#includequeue。 二、priority_queue类常用接口
函数名称功能说明priority_queue()构造一个空的优先级队列priority_queue(first,last)构造一个空的优先级队列empty()检测优先级队列是否为空是返回true否则返回falsetop( )返回优先级队列中最大/最小元素即堆顶元素push(X)在优先级队列中插入元素Xpop()删除优先级队列中最大/最小元素即堆顶元素priority_queue类常用接口应用
#includeiostream
#includequeue
#includevector
#includefunctional
using namespace std;int main()
{vectorint v { 10,60,50,20 };//priority_queueint pq;priority_queueint pq(v.begin(),v.end());pq.push(30);while (!pq.empty()){cout pq.top() ;pq.pop();}return 0;
}三、priority_queue类的使用
切换大小堆 默认情况下priority_queue是创建的是大堆其底层按照小于号比较默认模板参数为templateclass T, class Container std::vectorT, class Compare std::lessT如果要创建小堆将第三个模板参数换成greater即可例如priority_queueint, vectorint, greaterint pq2(v.begin(), v.end()); greaterint和lessT greater和less的头文件为#include functional具体实现见第三节模拟实现部分。 functional是C标准库中的一个头文件定义了C标准中多个用于表示函数对象的类模板包括算法操作、比较操作、逻辑操作 建堆时lessT是大顶堆堆元素是从大到小greaterT是小顶堆堆元素是从小到大。 排序时lessT是升序数组元素是从小到大greaterT是降序堆数组元素是从大到小。 如果priority_queue中放自定义类型的数据需要在自定义类型中提供 或者 的重载
class Date
{
public:Date(int year 2023, 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_queueDate q1;q1.push(Date(2023, 1, 2));q1.push(Date(2023, 1, 3));q1.push(Date(2023, 1, 4));cout q1.top() endl;// 如果要创建小堆需要用户提供的重载priority_queueDate, vectorDate, greaterDate q2;q2.push(Date(2023, 1, 2));q2.push(Date(2023, 1, 3));q2.push(Date(2023, 1, 4));cout q2.top() endl;
}四、STL中priority_queue类的模拟实现
#pragma once
#includevectornamespace MyPriority_queue
{templateclass Tstruct less{bool operator()(const T l, const T r){return l r;}};templateclass Tstruct greater{bool operator()(const T l, const T r){return l r;}};templateclass T, class Container std::vectorT, class Compare std::lessTclass priority_queue{public://typedef typename Container::value_type VT;void AdjustUp(size_t child){Compare com;size_t parent (child - 1) / 2;while (child 0){//if (_con[parent] _con[child])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 AdjustDwon(size_t parent){Compare com;size_t child parent * 2 1;while (child _con.size()){//if (child1 _con.size() _con[child] _con[child1])if (child 1 _con.size() com(_con[child], _con[child 1])){child;}//if (_con[parent] _con[child])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDwon(0);}T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}
