STL——priority_queue

一、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。

注意：

（1）priority_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（建大堆）template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue {public:priority_queue():_con(){}//区间构造template<class Iterator>priority_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;};
}