河间市网站建设价格,网页设计与制作项目教程第二版,求职网站建设,商标注册代理一、priority_queue介绍及使用
1.priority_queue文档介绍
#xff08;1#xff09;优先队列是一种容器适配器#xff0c;根据严格的弱排序标准#xff0c;它的第一个元素总是它所包含的元素中最大的。
#xff08;2#xff09;此上下文类似与堆#xff0c;在堆中可以…一、priority_queue介绍及使用
1.priority_queue文档介绍
1优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。
2此上下文类似与堆在堆中可以随时插入元素并且只能检索最大堆元素优先队列中位于顶部的元素。
3优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。
4底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 ①empty检测容器是否为空 ②size返回容器中有效元素的个数 ③front返回容器中第一个元素的引用 ④push_back在容器尾部插入元素 ⑤pop_back删除容器尾部元素。 5标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。
6需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
2.priority_queue的使用 优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用堆算法将vector中元素构造成堆的结构因此priority_queue就是堆。所以遇到需要用到堆的时候就可以考虑使用priority_queue。
注意
1priority_queue的模板参数列表 2默认情况下priority_queue内采用的是less比较构造的是大堆。
3若要构造小堆需要显示的提供比priority_queue第三个参数比较方法为greater头文件为functional)。
4存放数据为自定义类型时less和greater比较方法就不适用了。解决方法①自己定义比较函数通过函数指针的方式将函数类型传递进去②定义仿函数函数对象在类中对()进行重载这样类对象就可以像函数一样被调用
常用接口介绍 二、模拟实现priority_queue
#include iostream
#include vector
#include functional
#include assert.h
using namespace std;namespace MyPriority_queue {//默认底层容器采用vector比较方法为less建大堆templateclass T, class Container vectorT, class Compare lessTclass priority_queue {public:priority_queue():_con(){}//区间构造templateclass Iteratorpriority_queue(Iterator first, Iterator last): _con(first, last){//调整为堆for (int root (_con.size() - 2) / 2; root 0; --root) {//从倒数第一个非叶子节点开始向下调整AdjustDown(root);}}void push(const T val) {_con.push_back(val);//向上调整AdjustUp(_con.size() - 1);}void pop() {if (empty()) assert(0);//交换堆顶和末尾出队队尾对堆顶进行调整swap(_con.front(), _con.back());_con.pop_back();AdjustDown(0);}size_t size() const {return _con.size();}bool empty() {return _con.empty();}const T top() const {//注意堆顶不能被修改return _con.front();}private:void AdjustDown(size_t parent) {size_t child parent * 2 1;//左孩子size_t size _con.size();Compare com;//创建比较对象while (child size) {if (child 1 size com(_con[child], _con[child 1])) {child 1;//注意标记的是右孩子所以上面的比较方法传值时要先传左}//检测双亲节点是否满足堆的特性if (com(_con[parent], _con[child])) {//不满足则交换比继续向下调整swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else {return;}}}void AdjustUp(size_t child) {size_t parent (child - 1) / 2;Compare com;while (child) {if (com(_con[parent], _con[child])) {swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else {return;}}}private:Container _con;};
}
