网站设计机构图,网站开发进阶,河南网站建设详细流程,资源wordpress#x1f4d8;北尘_#xff1a;个人主页 #x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上#xff0c;不忘来时的初心 文章目录 一、priority_queue的介绍和使用1、priority_queue的介绍2、priority_queue的使用 二、priori… 北尘_个人主页 个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上不忘来时的初心 文章目录 一、priority_queue的介绍和使用1、priority_queue的介绍2、priority_queue的使用 二、priority_queue的模拟实现1、无仿函数2、带仿函数 一、priority_queue的介绍和使用
1、priority_queue的介绍
优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元 素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问并支持以下操作 empty()检测容器是否为空 size()返回容器中有效元素个数 front()返回容器中第一个元素的引用 push_back()在容器尾部插入元素 pop_back()删除容器尾部元素标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指 定容器类则使用vector。需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作。
2、priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成 堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意 默认情况下priority_queue是大堆。
默认情况下priority_queue是大堆 如果要建小堆需要改变条件 如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供 或者 的重载。
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_queueDate q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout q1.top() endl;// 如果要创建小堆需要用户提供的重载priority_queueDate, vectorDate, greaterDate 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的模拟实现
1、无仿函数
namespace bit
{templateclass T , class Container vectorintclass priority_queue{public:void adjust_up(int child){int parent (child - 1) / 2;while (child 0){if (_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);adjust_up(_con.size() - 1);}void adjust_down(int parent){int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child 1] _con[child]){child;}if (_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();adjust_down(0);}bool empty(){return _con.empty();}const T top(){return _con[0];}private:Container _con;};
}2、带仿函数
namespace bit
{templateclass T , class Container vectorint,class CompareLessTclass priority_queue{public:void adjust_up(int child){Compare com;int 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 push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){Compare com;size_t child parent * 2 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 parent * 2 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}const T top(){return _con[0];}private:Container _con;};}int main()
{bit::priority_queueint,vectorint,Lessint v;v.push(1);v.push(9);v.push(8);while (!v.empty()){cout v.top() ;v.pop();}return 0;
}
