priority_queue：优先队列

顾名思义，这个东西可以用于存放单调的数据，后面将会看到用于优化Dijkstra

有3个类函数：

void push(元素类型   变量)

void pop()

int top()

int size()

bool empty()

分别是：

• 加入类型是XXX的变量XXX
• 弹出队列首元素
• 取优先队列的队首元素的值
• 返回队列元素数量
• 查看队列是否为空

定义：

1. priority_queue <数据类型，容器类型，元素比较方式>
2. priority_queue <数据类型，容器类型>
3. priority_queue <数据类型>

数据类型：int,double.....

容器类型：vector（默认），deque，但不能是list

元素比较方式：less（默认，不上升序），greater（不下降序）

比如要定义一个元素值为整数，容器为vector<int>的不下降序的优先队列PQ：

priority_queue <int,vector<int> ,greater<int> >PQ

如果是第3种定义方式，容器默认为vector，比较方式默认是less（第二种的默认比较方式也是less）

实用的例子：

堆优化的Dijkstra算法，写出堆不难，但麻烦，如果想更快的写出高效的Dijkstra，用priority_queue就很不错：

#include <queue>
priority_queue <pair<int ,int>,vector<pair<int ,int> >,greater<pair<int,int> > > PQ;

void Dijkstra()
{
	while(!PQ.empty())
		PQ.pop();
	MC[1]=0;
	PQ.push(pair<int,int>(MC[1],1));
	while(!PQ.empty())
	{
	int Index=PQ.top().second;
		PQ.pop();
		if(!flag[Index])
		{
			flag[Index]=true;
			for(Node *p=last[Index];p;p=p->Prev)
				if(!flag[p->Name] && MC[p->Name]>MC[Index]+p->Dis)
				{
					MC[p->Name]=MC[Index]+p->Dis;
					PQ.push(pair<int,int>(MC[p->Name],p->Name));
				}
		}
	}
}

MC是最小花费

flag标志数组

last 邻接表

更详细的信息请参阅：

http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

参考

cplusplus.com

http://blog.chinaunix.net/space.php?uid=533684&do=blog&cuid=2615612