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：

 

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

 

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

实用的例子：

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

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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