#include<queue>

头文件 queue 主要包含循环队列 queue 和优先队列 priority_queue 两个容器

声明

queue<int> que;

struct node
{
//...
};
queue<node>que;

priority_queue<int>que;
priority_queue< pair<int ,int> >que;

[pair<>注释]：C++内置的二元组，尖括号中分别指定二元组的第一元、第二元的类型。可以用make_pair函数创建二元组，用成员变量first访问第一元，second访问第二元。在比较大小时，以第一元为第一关键字、第二元为第二关键字。

循环队列 queue

优先队列priority_queue

priority_queue可理解为一个大根二叉堆。

重载<运算符

priority_queue中存储的元素类型必须定义"小于号"，较大的元素会被放在堆顶内置的 int ,string 等类型本身就可以比较大小，若使用自定义的结构体类型，则需要重载<运算符。

例如下面的poi结构体保存了二维平面上点的编号和坐标，比较大小时，先比较横坐标，再比较纵坐标，并且考虑了精度误差：

struct poi{ int id; double x,y;};
const double eps=1e-8;

bool operator <(const poi &a,const poi &b){
       return a.x + eps < b.x || a.x < b.x +eps && a.y<b.y;
}

priority_queue 实现小根堆

priority_queue 实现小根二叉堆的方式一般有两种。（priority_queue默认是大根堆）

对于 int 等内置数值类型，可以把要插入的元素的相反数放入堆中。等从堆中取出元素时，再把它取一次相反数就变回原理的元素。这样就相当于把小的放在堆顶。

例如要插入 1，2，3 三个数时，改为插入 -1，-2，-3 ，此时 -1 最大，处于堆顶，把 -1 取出后再变回 -(-1) ,相当于取出了最小的 1。

或者利用 greator<> 实现小根堆。

//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

更为通用的解决方案是，建立自定义结构体类型，重载“小于号”，但是当作“大于号”来编写函数，例如：

struct node{ int id; double val; };
bool operator<(const node &a,const node &b){
     return a.value>b.value;  //按照val值排序
}

这样 priority_queue 会认为“大”的更“小”，“小”的更“大”，从而实现大根堆时，value较小的 node 元素会被放在堆顶。

懒惰删除法

利用数组手写堆，可以删除数组下标为k的的节点（注意下标为k,不是第k大，所以实际用途并不大），但STL的"优先队列"却并不支持删除堆中任意元素，这给我们带来了很多不便。（如果能删除第k大，或更新任意一个元素值，其作用等价于平衡树）

懒惰删除法（又称为延迟删除法）就是一种应对策略。当遇到删除操作时，仅在优先队列之外做一些特殊的记录（例如记录元素的最新值），用于辨别那些堆中尚未清除的“过时”元素。当从堆顶取出最值时，再检查“最值元素” 是不是“过时”的，若是，则重新取出下一个最值。换言之，元素的“删除”被延迟到堆顶进行。（如果有“更新”，平衡树功能更强大）

在“堆优化Dijstra/SPFA算法”中，当一个节点的距离值 dist[y] 被更新时（被松弛），暂时不更新优先队列中 y 对应的元素，而是直接把新的二元组（-dist[y],y）插入优先队列。

当堆顶取出二元组（val,x）准备扩展时，检查dist[x]是否等于-val, 如果不相等，那么说明这个元素是被删除过的，此时直接继续循环，取下一个堆顶。

学习完毕

{{ select(1) }}

• YES
• NO