[关闭]
@Archger 2016-07-10T03:23:14.000000Z 字数 10004 阅读 3417

C++优先队列详解

ACM STL 优先队列 priority_queue

优先队列：顾名思义，首先它是一个队列，但是它强调了“优先”二字，所以，已经不能算是一般意义上的队列了，它的“优先”意指取队首元素时，有一定的选择性，即根据元素的属性选择某一项值最优的出队~
百度百科上这样描述的：
　　优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素
　　优先队列的类定义　　
　　优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priorityq u e u e)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.
优先队列，其构造及具体实现我们可以先不用深究，我们现在只需要了解其特性，及在做题中的用法，相信，看过之后你会收获不少。
使用优先队列，首先要包函STL头文件"queue"，
以一个例子来解释吧(呃，写完才发现，这个代码包函了几乎所有我们要用到的用法，仔细看看吧)：

  1. /*优先队列的基本使用    2010/7/24    dooder*/  
  2. #include<stdio.h>  
  3. #include<functional>  
  4. #include<queue>  
  5. #include<vector>  
  6. using namespace std;  
  7. //定义结构，使用运算符重载,自定义优先级1  
  8. struct cmp1{  
  9.     bool operator ()(int &a,int &b){  
  10.         return a>b;//最小值优先  
  11.     }  
  12. };  
  13. struct cmp2{  
  14.     bool operator ()(int &a,int &b){  
  15.         return a<b;//最大值优先  
  16.     }  
  17. };  
  18. //定义结构，使用运算符重载,自定义优先级2  
  19. struct number1{  
  20.     int x;  
  21.     bool operator < (const number1 &a) const {  
  22.         return x>a.x;//最小值优先  
  23.     }  
  24. };  
  25. struct number2{  
  26.     int x;  
  27.     bool operator < (const number2 &a) const {  
  28.         return x<a.x;//最大值优先  
  29.     }  
  30. };  
  31. int a[]={14,10,56,7,83,22,36,91,3,47,72,0};  
  32. number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0};  
  33. number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0};  
  35. int main()  
  36. {   priority_queue<int>que;//采用默认优先级构造队列  
  38.     priority_queue<int,vector<int>,cmp1>que1;//最小值优先  
  39.     priority_queue<int,vector<int>,cmp2>que2;//最大值优先  
  41.     priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误，  
  42.                                                       //这是右移运算符，所以这里用空格号隔开  
  43.     priority_queue<int,vector<int>,less<int> >que4;////最大值优先  
  45.     priority_queue<number1>que5;  
  46.     priority_queue<number2>que6;  
  48.     int i;  
  49.     for(i=0;a[i];i++){  
  50.         que.push(a[i]);  
  51.         que1.push(a[i]);  
  52.         que2.push(a[i]);  
  53.         que3.push(a[i]);  
  54.         que4.push(a[i]);  
  55.     }  
  56.     for(i=0;num1[i].x;i++)  
  57.         que5.push(num1[i]);  
  58.     for(i=0;num2[i].x;i++)  
  59.         que6.push(num2[i]);  
  62.     printf("采用默认优先关系:\n(priority_queue<int>que;)\n");  
  63.     printf("Queue 0:\n");  
  64.     while(!que.empty()){  
  65.         printf("%3d",que.top());  
  66.         que.pop();  
  67.     }  
  68.     puts("");  
  69.     puts("");  
  71.     printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n");  
  72.     printf("Queue 1:\n");  
  73.     while(!que1.empty()){  
  74.         printf("%3d",que1.top());  
  75.         que1.pop();  
  76.     }  
  77.     puts("");  
  78.     printf("Queue 2:\n");  
  79.     while(!que2.empty()){  
  80.         printf("%3d",que2.top());  
  81.         que2.pop();  
  82.     }  
  83.     puts("");  
  84.     puts("");  
  85.     printf("采用头文件\"functional\"内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n");  
  86.     printf("Queue 3:\n");  
  87.     while(!que3.empty()){  
  88.         printf("%3d",que3.top());  
  89.         que3.pop();  
  90.     }  
  91.     puts("");  
  92.     printf("Queue 4:\n");  
  93.     while(!que4.empty()){  
  94.         printf("%3d",que4.top());  
  95.         que4.pop();  
  96.     }  
  97.     puts("");  
  98.     puts("");  
  99.     printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n");  
  100.     printf("Queue 5:\n");  
  101.     while(!que5.empty()){  
  102.         printf("%3d",que5.top());  
  103.         que5.pop();  
  104.     }  
  105.     puts("");  
  106.     printf("Queue 6:\n");  
  107.     while(!que6.empty()){  
  108.         printf("%3d",que6.top());  
  109.         que6.pop();  
  110.     }  
  111.     puts("");  
  112.     return 0;  
  113. }  
  114. /* 
  115. 运行结果 ： 
  116. 采用默认优先关系: 
  117. (priority_queue<int>que;) 
  118. Queue 0: 
  119. 83 72 56 47 36 22 14 10  7  3 
  121. 采用结构体自定义优先级方式一: 
  122. (priority_queue<int,vector<int>,cmp>que;) 
  123. Queue 1: 
  124.  7 10 14 22 36 47 56 72 83 91 
  125. Queue 2: 
  126. 83 72 56 47 36 22 14 10  7  3 
  128. 采用头文件"functional"内定义优先级: 
  129. (priority_queue<int,vector<int>,greater<int>/less<int> >que;) 
  130. Queue 3: 
  131.  7 10 14 22 36 47 56 72 83 91 
  132. Queue 4: 
  133. 83 72 56 47 36 22 14 10  7  3 
  135. 采用结构体自定义优先级方式二: 
  136. (priority_queue<number>que) 
  137. Queue 5: 
  138.  7 10 14 22 36 47 56 72 83 91 
  139. Queue 6: 
  140. 83 72 56 47 36 22 14 10  7  3 
  141. */  
  142. 运行结果：
  143. 采用默认优先关系:
  144. (priority_queue<int>que;)
  145. Queue 0:
  146. 83 72 56 47 36 22 14 10  7  3
  147. 采用结构体自定义优先级方式一:
  148. (priority_queue<int,vector<int>,cmp>que;)
  149. Queue 1:
  150.  7 10 14 22 36 47 56 72 83 91
  151. Queue 2:
  152. 83 72 56 47 36 22 14 10  7  3
  153. 采用头文件"functional"内定义优先级:
  154. (priority_queue<int,vector<int>,greater<int>/less<int> >que;)
  155. Queue 3:
  156.  7 10 14 22 36 47 56 72 83 91
  157. Queue 4:
  158. 83 72 56 47 36 22 14 10  7  3
  159. 采用结构体自定义优先级方式二:
  160. (priority_queue<number>que)
  161. Queue 5:
  162.  7 10 14 22 36 47 56 72 83 91
  163. Queue 6:
  164. 83 72 56 47 36 22 14 10  7  3
  165. 好了，如果你仔细看完了上面的代码，那么你就可以基本使用优先队列了，下面给出一些我做题中有过的一些应用，希望能给大家带来一些启
  166. 示~
  167. 1、先来一个我们最近做的题吧，http://acm.hdu.edu.cn/showproblem.php?pid=1242
  168. 题意：某人被关在囚笼里等待朋友解救，问能否解救成功，最少需要多少时间~
  169. 具体：可同时有几个朋友，每走一格消耗一分钟的时间 ，地图上还存在着卫兵，卫兵可以解决掉，但是要另外花费一分钟~
  170. 分析：从“a”出发，此题可以用回溯法进行深搜，但那样做的话，效率还是不能让人满意，但是广搜的话，由于入队后每次出队时，根据地
  171. 图情况的不同，出队元素所记忆的时间并不是层次递增的，因此使用简单广搜的话，同样需要全部搜索才能找到正确答案。有没有一种方法能
  172. 让某一步因为遇到士兵而多花时间的结点在队列中向后推迟一层出队呢？答案是肯定的，在这里我们可以用优先队列来实现，总体思想上是，
  173. 根据时间进行优先性选择，每次都要出队当前队列元素中记录时间最少的出队，而入队处理时，我们可以按顺序对四个方向上的各种情况按正
  174. 常处理入队就行了，出队顺序由优先队列根据预设优先性自动控制。这样，我们就可以从“a”进行基于优先队列的范围搜索了，并且在第一
  175. 次抵达有朋友的位置时得到正确结果~具体实现代码：
  176. view plaincopy to clipboardprint?
  177. /*HDU 1242  基于优先队列的范围搜索，16ms   dooder*/  
  179. #include<stdio.h>  
  180. #include<queue>  
  181. using namespace std;  
  183. #define M 201  
  184. typedef struct p{  
  185.     int x,y,t;  
  186.     bool operator < (const p &a)const  
  187.     {  
  188.         return t>a.t;//取时间最少优先  
  189.     }  
  190. }Point;  
  192. char map[M][M];  
  193. Point start;  
  194. int n,m;  
  195. int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}};  
  197. int bfs()  
  198. {  
  199.     priority_queue<Point>que;  
  200.     Point cur,next;  
  201.     int i;  
  203.     map[start.x][start.y]='#';  
  204.     que.push(start);  
  205.     while(!que.empty()){  
  206.         cur=que.top();//由优先队列自动完成出队时间最少的元素  
  207.         que.pop();  
  208.         for(i=0;i<4;i++){  
  209.             next.x=cur.x+dir[i][0];  
  210.             next.y=cur.y+dir[i][1];  
  211.             next.t=cur.t+1;  
  212.             if(next.x<0||next.x>=n||next.y<0||next.y>=m)  
  213.                 continue;  
  214.             if(map[next.x][next.y]=='#')  
  215.                 continue;  
  216.             if(map[next.x][next.y]=='r')  
  217.                 return next.t;  
  218.             if(map[next.x][next.y]=='.'){  
  219.                 map[next.x][next.y]='#';  
  220.                 que.push(next);  
  221.             }  
  222.             else if(map[next.x][next.y]=='x'){  
  223.                 map[next.x][next.y]='#';  
  224.                 next.t++;  
  225.                 que.push(next);  
  226.             }  
  227.         }  
  228.     }  
  229.     return -1;  
  230. }  
  231. int main()  
  232. {  
  233.     int i,ans;  
  234.     char *p;  
  235.     while(scanf("%d%d",&n,&m)!=-1){  
  236.         for(i=0;i<n;i++){  
  237.             scanf("%s",map[i]);  
  238.             if(p=strchr(map[i],'a')){  
  239.                 start.x=i;  
  240.                 start.y=p-map[i];  
  241.                 start.t=0;  
  242.             }  
  243.         }  
  244.         ans=bfs();  
  245.         printf(ans+1?"%d\n":"Poor ANGEL has to stay in the prison all his life.\n",ans);  
  246.     }  
  247.     return 0;  
  248. }  
  249. 2、http://acm.hdu.edu.cn/showproblem.php?pid=1053
  250. 题意：给出一行字符串，求出其原编码需要的编码长度和哈夫曼编码所需的长度，并求其比值
  251. 分析：根据哈夫曼生成树的生成过程可知，其生成树的权值是固定的而且这个值是最小的，而且其值根据生成树的顺序，我们可以找出规律而
  252. 不需要真的去生成一棵树然后再求出权值，其模拟过程为取出队列中权值最小的两个元素，将其值加入结果中，然后将这两个元素的权值求和
  253. 即得出其父节点的权值，将生成元素作为结点入队~~如此循环，直至取出队列中最后两个元素加入结果，实现代码如下：
  254. view plaincopy to clipboardprint?
  255. /*HDU 1053  采用广搜求哈夫曼生成树的权值 0ms   dooder*/  
  256. #include<stdio.h>  
  257. #include<string.h>  
  258. #include<ctype.h>  
  259. #include<functional>  
  260. #include<queue>  
  261. using namespace std;  
  262. #define M 1000050  
  263. char str[M];  
  264. int list[27];  
  266. priority_queue< int,vector<int>,greater<int> >que;  
  268. int main()  
  269. {  
  270.     int ans,sum;  
  271.     int i,a,b,c;  
  272.     while(scanf("%s",str),strcmp(str,"END")){  
  273.         memset(list,0,sizeof(list));  
  274.         for(i=0;str[i];i++){  
  275.             if(isalpha(str[i]))  
  276.                 list[str[i]-'A']++;  
  277.             else  
  278.                 list[26]++;  
  279.         }  
  280.         sum=i*8;ans=i;c=0;  
  281.         for(i=0;i<27;i++){  
  282.             if(list[i]){  
  283.                 que.push(list[i]);  
  284.                 c++;  
  285.             }  
  286.         }         
  287.         if(c>1){ans=0;//注意只有一种字符的情况  
  288.             while(que.size()!=1){  
  289.                 a=que.top();  
  290.                 que.pop();  
  291.                 b=que.top();  
  292.                 que.pop();  
  293.                 ans+=a+b;  
  294.                 que.push(a+b);  
  295.             }  
  296.             while(!que.empty())//使用后清空队列  
  297.                 que.pop();  
  298.         }  
  299.         printf("%d %d %.1f\n",sum,ans,1.0*sum/ans);  
  300.     }  
  301.     return 0;  
  302. }  
  303. 3、http://acm.pku.edu.cn/JudgeOnline/problem?id=2263
  304. 这是第二次练习赛时，我们做过的最后一题，这里采用优先队列进行实现，在《谁说不能这样做题》中已提到这种方法，在这里再次放出代
  305. 码，~
  306. 题意：给出各城市间道路的限制载重量，求出从一个城市到另外一个城市的贷车能够运载的最大货物重量。
  307. 分析：采用优先队列，每次取出当前队列中结点的minheavy最大值出队，对它的连接结点搜索入队,这样，从出发点开始就可以
  308. 在到达终点时求出结果，即最大载货物重，实现代码如下：
  309. view plaincopy to clipboardprint?
  310. /*POJ 2263  16ms  dooder*/  
  312. #include<stdio.h>  
  313. #include<string.h>  
  314. #include<queue>  
  315. using namespace std;  
  316. #define M 201  
  317. typedef struct w{  
  318.     int city;  
  319.     int mintons;  
  320.     bool operator < (const w &a)const {  
  321.         return mintons < a.mintons;  
  322.     }//优先性定义  
  323. }Way;  
  324. char citys[M][31];  
  325. int map[M][M];  
  326. bool mark[M][M];  
  327. int n,m,from,to,ans,k;  
  328. priority_queue <Way> que;  
  329. int min(int a,int b)  
  330. {  
  331.     return a>b?b:a;  
  332. }  
  333. void bfs()  
  334. {  
  335.     Way cur,next;  
  336.     int i;  
  337.     while(!que.empty()){  
  338.         cur=que.top();  
  339.         que.pop();  
  340.         if(cur.city==to){  
  341.             if(cur.mintons>ans)  
  342.                 ans=cur.mintons;  
  343.             while(!que.empty())  
  344.                 que.pop();  
  345.             return ;  
  346.         }  
  347.         for(i=0;i<n;i++){  
  348.             if(map[cur.city][i]&&!mark[cur.city][i]){  
  349.                 next.city=i;  
  350.                 next.mintons=min(cur.mintons,map[cur.city][i]);  
  352.                 mark[cur.city][i]=mark[i][cur.city]=1;  
  353.                 que.push(next);  
  354.             }  
  355.         }  
  356.     }  
  357. }  
  358. void run()  
  359. {  
  360.     int i,temp,index;  
  361.     Way cur;  
  362.     ans=0;  
  363.     memset(mark,0,sizeof(mark));  
  364.     temp=0;  
  365.     for(i=0;i<n;i++){  
  366.         if(map[from][i]>temp){  
  367.             temp=map[from][i];  
  368.             index=i;  
  369.         }  
  370.     }  
  371.     cur.city=index;  
  372.     cur.mintons=temp;  
  373.     que.push(cur);  
  374.     bfs();  
  375. }  
  376. int main()  
  377. {  
  378.     int k1,k2,tons,t=1;  
  379.     char s1[31],s2[31];  
  380.     while(scanf("%d%d",&n,&m),n||m){  
  381.         k=0;  
  382.         while(m--){  
  383.             scanf("%s%s%d",s1,s2,&tons);  
  384.             for(k1=0;strcmp(s1,citys[k1])&&k1<k;k1++);  
  385.             if(k1==k)  
  386.                 strcpy(citys[k++],s1);  
  387.             for(k2=0;strcmp(s2,citys[k2])&&k2<k;k2++);  
  388.             if(k2==k)  
  389.                 strcpy(citys[k++],s2);  
  390.             map[k1][k2]=map[k2][k1]=tons;  
  391.         }  
  392.         scanf("%s%s",s1,s2);  
  393.         for(from=0;strcmp(citys[from],s1);from++);  
  394.         for(to=0;strcmp(citys[to],s2);to++);  
  395.         run();  
  396.         printf("Scenario #%d\n",t++);  
  397.         printf("%d tons\n\n",ans);  
  398.     }  
  399.     return 0;  
  400. }  
  401. 当然了，优先队列的用法决不是仅仅提到的这些，各种应用还需要大家去发现，给道题大家可以练习一下hdu 2066\
  402. 相信大家已经学到不少了，还有一点可以告诉大家，优先队列是启发式搜索的数据结构基础，希望好好理解，并逐步掌握其用法~
  403.  加：失策啊，竟然忘了说优先队列的效率了，其时间复杂度为O(logn).n为队列中元素的个数，存取都需要消耗时间~
  1. #include<iostream>
  2. #include<functional>
  3. #include<queue>
  4. using namespace std;
  5. struct node
  6. {
  7.     friend bool operator< (node n1, node n2)
  8.     {
  9.         return n1.priority < n2.priority;//"<"为从大到小排列，">"为从小打到排列
  10.     }
  11.     int priority;
  12.     int value;
  13. };
  14. int main()
  15. {
  16.     const int len = 5;
  17.     int i;
  18.     int a[len] = {3,5,9,6,2};
  19.     //示例1
  20.     priority_queue<int> qi;//普通的优先级队列，按从大到小排序
  21.     for(i = 0; i < len; i++)
  22.         qi.push(a[i]);
  23.     for(i = 0; i < len; i++)
  24.     {
  25.         cout<<qi.top()<<" ";
  26.         qi.pop();
  27.     }
  28.     cout<<endl;
  29.     //示例2
  30.     priority_queue<int, vector<int>, greater<int> > qi2;//从小到大的优先级队列，可将greater改为less，即为从大到小
  31.     for(i = 0; i < len; i++)
  32.         qi2.push(a[i]);
  33.     for(i = 0; i < len; i++)
  34.     {
  35.         cout<<qi2.top()<<" ";
  36.         qi2.pop();
  37.     }
  38.     cout<<endl;
  39.     //示例3
  40.     priority_queue<node> qn;//必须要重载运算符
  41.     node b[len];
  42.     b[0].priority = 6; b[0].value = 1;
  43.     b[1].priority = 9; b[1].value = 5;
  44.     b[2].priority = 2; b[2].value = 3;
  45.     b[3].priority = 8; b[3].value = 2;
  46.     b[4].priority = 1; b[4].value = 4;
  48.     for(i = 0; i < len; i++)
  49.         qn.push(b[i]);
  50.     cout<<"优先级"<<'\t'<<"值"<<endl;
  51.     for(i = 0; i < len; i++)
  52.     {
  53.         cout<<qn.top().priority<<'\t'<<qn.top().value<<endl;
  54.         qn.pop();
  55.     }
  56.     return 0;
  57. }

对于队列里元素为一个结构体类型，按照某一个属性排序，就需要对比较函数进行重载
小结一下：

1、若是定义值类型对象，如：

  1. int  main() 
  2. {      
  3.     priority_queue<node> qn;
  4.     node n1; 
  5.     n1.a = 9; 
  6.     node n2; 
  7.     n2.a = 2; 
  8.     node n3; 
  9.     n3.a = 50;  
  10.     qn.push(n1);
  11.     qn.push(n2);
  12.     qn.push(n3);
  13.      int  size = qn.size();
  14.      for ( int  i = 0; i < size; i++) 
  15.     { 
  16.         cout << qn.top().a << endl;
  17.         qn.pop(); 
  18.     } 
  19.          return  0;
  20. }

则定义优先级的时候，直接在类中写个friend 的操作符重载函数即可： 

  1. class  node 
  2. { 
  3. public : 
  4.      int  a;
  5.     node(){} 
  6.     node( int  x):a(x){} 
  7. friend   bool  operator<( const  node ne1, const  node ne2)//参数也可以为引用，值传递 
  8.     { 
  9.          if (ne1.a > ne2.a) 
  10.         { 
  11.              return   true ; 
  12.         } 
  13.          else 
  14.         { 
  15.              return   false ; 
  16.         } 
  17.     } 
  18. };

其中在c＋＋primer第三版 中文版中关于操作符重载有如下描述：
"程序员只能为类类型或枚举类型的操作数定义重载操作符我们可以这样来实现把重
载操作符声明为类的成员或者声明为名字空间成员同时至少有一个类或枚举类型的参数
按值传递或按引用传递"
因此不可用指针类型的参数；

2、如果想定义一个指针类型的优先队列，那就不可这么简单的定义了，你需要自定义一个自己的比较函数，在priority_queue的模板函数中，我们可以利用这样一个template, class _Pr = less >模板，在我们的程序代码中，则需要自己定义一个类来定义第三个模板参数，如：

  1. class  nodePointerComparer  
  2. {  
  3. public :  
  4.     nodePointerComparer(){}  
  5.      bool  operator ()( const  node* ne1,  const  node* ne2)  const   
  6.     {  
  7.          return  ne1->lessthan(ne2);  
  8.     }  
  9. };

当然在这之前我们的类Node要重新书写 

  1. class  node  
  2. {  
  3. public :  
  4.      int  a;  
  5.     node(){}  
  6.     node( int  x):a(x){} 
  7.      bool  lessthan( const  node* pnode)  const   
  8.     {  
  9.          return  a < pnode->a;  
  10.     }  
  11. };

这样在main函数中就可以定义指针类型的优先队列了：

  1. int  main()  
  2. {  
  3.     priority_queue <node*, vector <node*>, nodePointerComparer> qn;  
  4.     node *n1 =  new  node(90);  
  5.     node *n2 =  new  node(2);  
  6.     node *n3 =  new  node(50); 
  7.     qn.push(n1);  
  8.     qn.push(n2); /span>> 
  9.     qn.push(n3); 
  10.      int  size = qn.size();  
  11.      for ( int  i = 0; i < size; i++)  
  12.     {  
  13.         cout << qn.top()->a << endl;  
  14.         qn.pop();  
  15.     }  
  16.      return  0; 
  17. }

疑问之处：如果你使用第一种值传递的操作符重载，来实现第二种的指针类型优先队列，是不会达到想要的结果的，个人理解是因为在指针类型的优先队列中找“<”运算符的时候，重载的不是我们写的值传递friend bool operator<(const node ne1,const node ne2)//
也就是没有找到指针类型的"<"重载，所有不会达到优先队列的效果。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注