优先队列

---

优先队列是通过二叉堆(heap)来维护的。

二叉堆(heap)是一棵满足以下条件的完全二叉树：

(1)若一个节点有子节点，且这个子节点大于父节点，我们就称之为小根堆；

(2)若一个节点有子节点，且这个子节点小于父节点，我们就称之为大根堆。

完全二叉树：

//             heap[i/2]   
//            /        \
//      heap[i]         heap[i+1]
//      /     \             /
//heap[i*2] heap[i*2+1] heap[(i+1)*2]

用数组模拟二叉堆（以维护小根堆为例）

---

1.插入：

插入一个数3在下面的二叉堆中

//           1              
//         /   \
//        2     4
//       / \   / \
//      5   6  7

思路：插入后，要维护子节点大于父节点，先将插入的3加入到队尾，在向上比较，如果父节点大于3，那么就交换两个数，知道父节点小于3为止。

//           1              
//         /   \
//        2     4
//       / \   / \
//      5   6  7  3 需要交换3和4

//           1              
//         /   \
//        2     3
//       / \   / \
//      5   6  7  4  成功!

代码实现：

void push(int x){
	heap[++len]=x;
	int p=len;
	while(heap[len]<heap[len>>1]){
		swap(heap[len],heap[len>>1]);
		p>>=1;
	}
	return;
}

2.删除：

目前我们维护的二叉堆只能实现根节点最小（或最大），所以删除根节点heap[1]，才是有意义的。

删除下面二叉堆的根节点1：

//           1              
//         /   \
//        2     3
//       / \   / \
//      5   6  7  8  

思路：在堆中直接删除根节点haep[1]，破坏了小根堆的性质（大根堆也一样），可以先用heap[n]来覆盖heap[1]，在向下调整。调整过程如下：

(1)找出当前节点p的两个子节点中更小的那个记为t；

(2)比较heap[t]与heap[p]的大小，若heap[t]>=heap[p]，即满足了小根堆的性质，就结束调整。否则交换heap[t]和heap[p]。

//           8              
//         /   \
//        2     3
//       / \   / \
//      5   6  7      需调整

//           2              
//         /   \
//        8     3
//       / \   / \
//      5   6  7      继续调整

//           2              
//         /   \
//        5     3
//       / \   / \
//      8   6  7       成功

代码实现：

void pop(){
	heap[1]=heap[len--];
	int p=1,t=1;//p是当前节点的编号 
	while(1){
		if(p<<1<=len&&heap[p<<1]<heap[p])t=p<<1;
		if(p<<1+1<=len&&heap[p<<1+1]<heap[t])t=p<<1+1;
		if(t==p)break;
		else{
			swap(heap[p],heap[t]);
			p=t;
		} 
	}
	return;
}

综上可得，用二叉堆维护优先队列效率高。

#include<iostream>
using namespace std;
int heap[1001],n,x,len;
void push(int x){
	heap[++len]=x;
	int p=len;
	while(heap[len]<heap[len>>1]){
		swap(heap[len],heap[len>>1]);
		p>>=1;
	}
	return;
}
void pop(){
	heap[1]=heap[len--];
	int p=1,t=1;//p是当前节点的编号 
	while(1){
		if(p<<1<=len&&heap[p<<1]<heap[p])t=p<<1;
		if(p<<1+1<=len&&heap[p<<1+1]<heap[t])t=p<<1+1;
		if(t==p)break;
		else{
			swap(heap[p],heap[t]);
			p=t;
		} 
	}
	return;
}
int main(){
  return 0;
}

以上是用数组模拟优先队列的运作原理。

priority_queue的应用

---

priority_queue（优先队列）是c++标准库中一个非常好用的容器，作为队列的延伸，其头文件也为<queue>。

定义方法如下：

priority_queue<Type,Container,Functional>

Type为数据类型，Container为保存数据的容器，Functional为元素比较方式。

Container必须为可以用数组实现的容器，如vector、deque等，但list不行。

STL中定义了两个仿函数，greater<Type> 和less<Type>，greater<Type>用来定义小根堆，less<Type>用来定义大根堆，具体用法如下：

priority_queue<int,vector<int>,greater<int> >q;//定义了一个名为q的小根堆

priority_queue<int,vector<int>,less<int> >q;//定义了一个名为q的大根堆
priority_queue<int>q;//定义了一个名为q的大根堆

这里有一点要特别注意：priority_queue<int,vector<int>,less<int> >q中两个尖括号要隔开，不然会报错。

以下是priority_queue的常用操作：

操作	功能描述	时间复杂度
push(element)	将元素插入队列	O(log n)
pop()	移除队首(最高优先级)元素
top()	访问队首元素(不删除)	O(1)
size()	返回队列中元素数量
empty()	检查队列是否为空

---

但在c++中，处理结构体的情况各位常见，那么如何处理结构体的排序呢？

例：输入多组x,y，把他们按x的大小从小到大排序，若x相等，按y的大小从小到大排序

方法一：使用重载运算符operator<

#include<iostream>
#include<queue> 
using namespace std;
struct node{int x,y;};
bool operator<(node a,node b){
	if(a.x==b.x)return a.y>b.y;//注意，小于号要变成大于号，因为我们声明了一个大根堆 
	return a.x>b.x;
}
priority_queue<node> q;//声明了大根堆 
int main(){
	int n,x,y;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		q.push((node){x,y});
	}
	while(!q.empty()){
		cout<<q.top().x<<" "<<q.top().y<<"\n";
		q.pop();
	}
}

这种写法有点过于臃肿，可以把重载运算符operator<写在结构体内

#include<iostream>
#include<queue> 
using namespace std;
struct node{
	int x,y;
	operator<(node a)const{//注意，这里有不同  
		if(a.x==x)return a.y<y;//注意，小于号不用变 
		return a.x<x;
	}
};
priority_queue<node> q;
int main(){
	int n,x,y;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		q.push((node){x,y});
	}
	while(!q.empty()){
		cout<<q.top().x<<" "<<q.top().y<<"\n";
		q.pop();
	}
}

方法二：自己写一个仿函数cmp，（有点类似sort()函数的cmp）

#include<iostream>
#include<queue> 
using namespace std;
struct node{int x,y;};
struct cmp{
	operator()(node a,node b){//注意，这里有不同  
		if(a.x==b.x)return a.y>b.y;//注意，小于号要变 
		return a.x>b.x;
	}
};
priority_queue<node,vector<node>,cmp> q;
int main(){
	int n,x,y;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		q.push((node){x,y});
	}
	while(!q.empty()){
		cout<<q.top().x<<" "<<q.top().y<<"\n";
		q.pop();
	}
}

个人认为还是方法一的第二种写法好，不过要注意不等号的方向要反过来。