优先队列详解(转载)

　优先队列是一种用来维护一组元素构成的结合S的数据结构，其中每个元素都有一个关键字key，元素之间的比较都是通过key来比较的。优先队列包括最大优先队列和最小优先队列，优先队列的应用比较广泛，比如作业系统中的调度程序，当一个作业完成后，需要在所有等待调度的作业中选择一个优先级最高的作业来执行，并且也可以添加一个新的作业到作业的优先队列中。Java中，PriorityQueue的底层数据结构就是堆（默认是小堆），关于Java的PriorityQueue更多知识请点击：深入理解Java PriorityQueue。

　　优先队列的实现中，我们可以选择堆数据结构，最大优先队列可以选用大堆，最小优先队列可以选用小堆来实现。下面以最大优先队列来讲解其原理。最大优先队列一般包括将一个元素插入到集合S中、返回集合S中具有最大key的元素、返回并删除集合S中具有最大key的元素等。

插入操作

　　插入操作是将一个元素插入到集合S中，首先把该元素放入所有元素的下一位置，然后执行“上浮”操作，如下图示例(注意，下图示例是小堆，不过原理是一样的，图片来自深入理解Java PriorityQueue)

)

移除操作

　　优先队列中，在队列非空情况下移除集合中第一个元素，也就是下标为0的元素，然后将集合中最后一个元素移到下标为0位置，在将下标为0的新元素执行“下沉”操作。如下图示例(注意，下图示例是小堆，不过原理是一样的，图片来自深入理解Java PriorityQueue)

完整代码实现

  1 package priorityheap;
  2 
  3 import java.util.Arrays;
  4 
  5 /**
  6  * 优先队列类（最大优先队列）
  7  */
  8 public class PriorityHeap {
  9 
 10     // ------------------------------ Instance Variables
 11 
 12     private int[] arr;
 13     private int size;
 14 
 15     // ------------------------------ Constructors
 16 
 17     /**
 18      * 优先队列数组默认大小为64
 19      */
 20     public PriorityHeap() {
 21         this(64);
 22     }
 23 
 24     public PriorityHeap(int initSize) {
 25         if (initSize <= 0) {
 26             initSize = 64;
 27         }
 28         this.arr = new int[initSize];
 29         this.size = 0;
 30     }
 31 
 32     // ------------------------------ Public methods
 33 
 34     public int max() {
 35         return this.arr[0];
 36     }
 37 
 38     public int maxAndRemove() {
 39         int t = max();
 40 
 41         this.arr[0] = this.arr[--size];
 42         sink(0, this.arr[0]);
 43         return t;
 44     }
 45     public void add(int data) {
 46         resize(1);
 47         this.arr[size++] = data;
 48         pop(size - 1, data);
 49     }
 50 
 51     // ------------------------------ Private methods
 52 
 53     /**
 54      * key下沉方法
 55      */
 56     private void sink(int i, int key) {
 57         while (2 * i <= this.size - 1) {
 58             int child = 2 * i;
 59             if (child < this.size - 1 && this.arr[child] < this.arr[child + 1]) {
 60                 child++;
 61             }
 62             if (this.arr[i] >= this.arr[child]) {
 63                 break;
 64             }
 65 
 66             swap(i, child);
 67             i = child;
 68         }
 69     }
 70 
 71     /**
 72      * key上浮方法
 73      */
 74     private void pop(int i, int key) {
 75         while (i > 0) {
 76             int parent = i / 2;
 77             if (this.arr[i] <= this.arr[parent]) {
 78                 break;
 79             }
 80             swap(i, parent);
 81             i = parent;
 82         }
 83     }
 84 
 85     /**
 86      * 重新调整数组大小
 87      */
 88     private void resize(int increaseSize) {
 89         if ((this.size + increaseSize) > this.arr.length) {
 90             int newSize = (this.size + increaseSize) > 2 * this.arr.length ? (this.size + increaseSize) : 2 * this.arr.length;
 91             int[] t = this.arr;
 92 
 93             this.arr = Arrays.copyOf(t, newSize);
 94         }
 95     }
 96 
 97     /**
 98      * Swaps arr[a] with arr[b].
 99      */
100     private void swap(int a, int b) {
101         int t = this.arr[a];
102         this.arr[a] = this.arr[b];
103         this.arr[b] = t;
104     }
105 }

实用方法

  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};  
 34   
 35 int main()  
 36 {   priority_queue<int>que;//采用默认优先级构造队列  
 37   
 38     priority_queue<int,vector<int>,cmp1>que1;//最小值优先  
 39     priority_queue<int,vector<int>,cmp2>que2;//最大值优先  
 40   
 41     priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误，  
 42                                                       //这是右移运算符，所以这里用空格号隔开  
 43     priority_queue<int,vector<int>,less<int> >que4;////最大值优先  
 44   
 45     priority_queue<number1>que5;  
 46     priority_queue<number2>que6;  
 47   
 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]);  
 60   
 61   
 62     printf("采用默认优先关系:
(priority_queue<int>que;)
");  
 63     printf("Queue 0:
");  
 64     while(!que.empty()){  
 65         printf("%3d",que.top());  
 66         que.pop();  
 67     }  
 68     puts("");  
 69     puts("");  
 70   
 71     printf("采用结构体自定义优先级方式一:
(priority_queue<int,vector<int>,cmp>que;)
");  
 72     printf("Queue 1:
");  
 73     while(!que1.empty()){  
 74         printf("%3d",que1.top());  
 75         que1.pop();  
 76     }  
 77     puts("");  
 78     printf("Queue 2:
");  
 79     while(!que2.empty()){  
 80         printf("%3d",que2.top());  
 81         que2.pop();  
 82     }  
 83     puts("");  
 84     puts("");  
 85     printf("采用头文件"functional"内定义优先级:
(priority_queue<int,vector<int>,greater<int>/less<int> >que;)
");  
 86     printf("Queue 3:
");  
 87     while(!que3.empty()){  
 88         printf("%3d",que3.top());  
 89         que3.pop();  
 90     }  
 91     puts("");  
 92     printf("Queue 4:
");  
 93     while(!que4.empty()){  
 94         printf("%3d",que4.top());  
 95         que4.pop();  
 96     }  
 97     puts("");  
 98     puts("");  
 99     printf("采用结构体自定义优先级方式二:
(priority_queue<number>que)
");  
100     printf("Queue 5:
");  
101     while(!que5.empty()){  
102         printf("%3d",que5.top());  
103         que5.pop();  
104     }  
105     puts("");  
106     printf("Queue 6:
");  
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  91 83 72 56 47 36 22 14 10  7  3 
120  
121 采用结构体自定义优先级方式一: 
122 (priority_queue<int,vector<int>,cmp>que;) 
123 Queue 1: 
124   3  7 10 14 22 36 47 56 72 83 91 
125 Queue 2: 
126  91 83 72 56 47 36 22 14 10  7  3 
127  
128 采用头文件"functional"内定义优先级: 
129 (priority_queue<int,vector<int>,greater<int>/less<int> >que;) 
130 Queue 3: 
131   3  7 10 14 22 36 47 56 72 83 91 
132 Queue 4: 
133  91 83 72 56 47 36 22 14 10  7  3 
134  
135 采用结构体自定义优先级方式二: 
136 (priority_queue<number>que) 
137 Queue 5: 
138   3  7 10 14 22 36 47 56 72 83 91 
139 Queue 6: 
140  91 83 72 56 47 36 22 14 10  7  3 
141 */

运行结果：
采用默认优先关系:
(priority_queue<int>que;)
Queue 0:
 91 83 72 56 47 36 22 14 10  7  3
采用结构体自定义优先级方式一:
(priority_queue<int,vector<int>,cmp>que;)
Queue 1:
  3  7 10 14 22 36 47 56 72 83 91
Queue 2:
 91 83 72 56 47 36 22 14 10  7  3
采用头文件"functional"内定义优先级:
(priority_queue<int,vector<int>,greater<int>/less<int> >que;)
Queue 3:
  3  7 10 14 22 36 47 56 72 83 91
Queue 4:
 91 83 72 56 47 36 22 14 10  7  3
采用结构体自定义优先级方式二:
(priority_queue<number>que)
Queue 5:
  3  7 10 14 22 36 47 56 72 83 91
Queue 6:
 91 83 72 56 47 36 22 14 10  7  3
好了，如果你仔细看完了上面的代码，那么你就可以基本使用优先队列了，下面给出一些我做题中有过的一些应用，希望能给大家带来一些启
示~

例题

1、先来一个我们最近做的题吧，http://acm.hdu.edu.cn/showproblem.php?pid=1242
题意：某人被关在囚笼里等待朋友解救，问能否解救成功，最少需要多少时间~
具体：可同时有几个朋友，每走一格消耗一分钟的时间 ，地图上还存在着卫兵，卫兵可以解决掉，但是要另外花费一分钟~
分析：从“a”出发，此题可以用回溯法进行深搜，但那样做的话，效率还是不能让人满意，但是广搜的话，由于入队后每次出队时，根据地
图情况的不同，出队元素所记忆的时间并不是层次递增的，因此使用简单广搜的话，同样需要全部搜索才能找到正确答案。有没有一种方法能
让某一步因为遇到士兵而多花时间的结点在队列中向后推迟一层出队呢？答案是肯定的，在这里我们可以用优先队列来实现，总体思想上是，
根据时间进行优先性选择，每次都要出队当前队列元素中记录时间最少的出队，而入队处理时，我们可以按顺序对四个方向上的各种情况按正
常处理入队就行了，出队顺序由优先队列根据预设优先性自动控制。这样，我们就可以从“a”进行基于优先队列的范围搜索了，并且在第一
次抵达有朋友的位置时得到正确结果~具体实现代码：

 1 /*HDU 1242  基于优先队列的范围搜索，16ms   dooder*/  
 2   
 3 #include<stdio.h>  
 4 #include<queue>  
 5 using namespace std;  
 6   
 7 #define M 201  
 8 typedef struct p{  
 9     int x,y,t;  
10     bool operator < (const p &a)const  
11     {  
12         return t>a.t;//取时间最少优先  
13     }  
14 }Point;  
15   
16 char map[M][M];  
17 Point start;  
18 int n,m;  
19 int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}};  
20   
21 int bfs()  
22 {  
23     priority_queue<Point>que;  
24     Point cur,next;  
25     int i;  
26   
27     map[start.x][start.y]='#';  
28     que.push(start);  
29     while(!que.empty()){  
30         cur=que.top();//由优先队列自动完成出队时间最少的元素  
31         que.pop();  
32         for(i=0;i<4;i++){  
33             next.x=cur.x+dir[i][0];  
34             next.y=cur.y+dir[i][1];  
35             next.t=cur.t+1;  
36             if(next.x<0||next.x>=n||next.y<0||next.y>=m)  
37                 continue;  
38             if(map[next.x][next.y]=='#')  
39                 continue;  
40             if(map[next.x][next.y]=='r')  
41                 return next.t;  
42             if(map[next.x][next.y]=='.'){  
43                 map[next.x][next.y]='#';  
44                 que.push(next);  
45             }  
46             else if(map[next.x][next.y]=='x'){  
47                 map[next.x][next.y]='#';  
48                 next.t++;  
49                 que.push(next);  
50             }  
51         }  
52     }  
53     return -1;  
54 }  
55 int main()  
56 {  
57     int i,ans;  
58     char *p;  
59     while(scanf("%d%d",&n,&m)!=-1){  
60         for(i=0;i<n;i++){  
61             scanf("%s",map[i]);  
62             if(p=strchr(map[i],'a')){  
63                 start.x=i;  
64                 start.y=p-map[i];  
65                 start.t=0;  
66             }  
67         }  
68         ans=bfs();  
69         printf(ans+1?"%d
":"Poor ANGEL has to stay in the prison all his life.
",ans);  
70     }  
71     return 0;  
72 }

2、http://acm.hdu.edu.cn/showproblem.php?pid=1053
题意：给出一行字符串，求出其原编码需要的编码长度和哈夫曼编码所需的长度，并求其比值
分析：根据哈夫曼生成树的生成过程可知，其生成树的权值是固定的而且这个值是最小的，而且其值根据生成树的顺序，我们可以找出规律而
不需要真的去生成一棵树然后再求出权值，其模拟过程为取出队列中权值最小的两个元素，将其值加入结果中，然后将这两个元素的权值求和
即得出其父节点的权值，将生成元素作为结点入队~~如此循环，直至取出队列中最后两个元素加入结果，实现代码如下：

 1 /*HDU 1053  采用广搜求哈夫曼生成树的权值 0ms   dooder*/  
 2 #include<stdio.h>  
 3 #include<string.h>  
 4 #include<ctype.h>  
 5 #include<functional>  
 6 #include<queue>  
 7 using namespace std;  
 8 #define M 1000050  
 9 char str[M];  
10 int list[27];  
11   
12 priority_queue< int,vector<int>,greater<int> >que;  
13   
14 int main()  
15 {  
16     int ans,sum;  
17     int i,a,b,c;  
18     while(scanf("%s",str),strcmp(str,"END")){  
19         memset(list,0,sizeof(list));  
20         for(i=0;str[i];i++){  
21             if(isalpha(str[i]))  
22                 list[str[i]-'A']++;  
23             else  
24                 list[26]++;  
25         }  
26         sum=i*8;ans=i;c=0;  
27         for(i=0;i<27;i++){  
28             if(list[i]){  
29                 que.push(list[i]);  
30                 c++;  
31             }  
32         }         
33         if(c>1){ans=0;//注意只有一种字符的情况  
34             while(que.size()!=1){  
35                 a=que.top();  
36                 que.pop();  
37                 b=que.top();  
38                 que.pop();  
39                 ans+=a+b;  
40                 que.push(a+b);  
41             }  
42             while(!que.empty())//使用后清空队列  
43                 que.pop();  
44         }  
45         printf("%d %d %.1f
",sum,ans,1.0*sum/ans);  
46     }  
47     return 0;  
48 }

 
3、http://acm.pku.edu.cn/JudgeOnline/problem?id=2263
这是第二次练习赛时，我们做过的最后一题，这里采用优先队列进行实现，在《谁说不能这样做题》中已提到这种方法，在这里再次放出代
码，~
题意：给出各城市间道路的限制载重量，求出从一个城市到另外一个城市的贷车能够运载的最大货物重量。
分析：采用优先队列，每次取出当前队列中结点的minheavy最大值出队，对它的连接结点搜索入队,这样，从出发点开始就可以
在到达终点时求出结果，即最大载货物重，实现代码如下：

 1 /*POJ 2263  16ms  dooder*/  
 2  
 3 #include<stdio.h>  
 4 #include<string.h>  
 5 #include<queue>  
 6 using namespace std;  
 7 #define M 201  
 8 typedef struct w{  
 9     int city;  
10     int mintons;  
11     bool operator < (const w &a)const {  
12         return mintons < a.mintons;  
13     }//优先性定义  
14 }Way;  
15 char citys[M][31];  
16 int map[M][M];  
17 bool mark[M][M];  
18 int n,m,from,to,ans,k;  
19 priority_queue <Way> que;  
20 int min(int a,int b)  
21 {  
22     return a>b?b:a;  
23 }  
24 void bfs()  
25 {  
26     Way cur,next;  
27     int i;  
28     while(!que.empty()){  
29         cur=que.top();  
30         que.pop();  
31         if(cur.city==to){  
32             if(cur.mintons>ans)  
33                 ans=cur.mintons;  
34             while(!que.empty())  
35                 que.pop();  
36             return ;  
37         }  
38         for(i=0;i<n;i++){  
39             if(map[cur.city][i]&&!mark[cur.city][i]){  
40                 next.city=i;  
41                 next.mintons=min(cur.mintons,map[cur.city][i]);  
42   
43                 mark[cur.city][i]=mark[i][cur.city]=1;  
44                 que.push(next);  
45             }  
46         }  
47     }  
48 }  
49 void run()  
50 {  
51     int i,temp,index;  
52     Way cur;  
53     ans=0;  
54     memset(mark,0,sizeof(mark));  
55     temp=0;  
56     for(i=0;i<n;i++){  
57         if(map[from][i]>temp){  
58             temp=map[from][i];  
59             index=i;  
60         }  
61     }  
62     cur.city=index;  
63     cur.mintons=temp;  
64     que.push(cur);  
65     bfs();  
66 }  
67 int main()  
68 {  
69     int k1,k2,tons,t=1;  
70     char s1[31],s2[31];  
71     while(scanf("%d%d",&n,&m),n||m){  
72         k=0;  
73         while(m--){  
74             scanf("%s%s%d",s1,s2,&tons);  
75             for(k1=0;strcmp(s1,citys[k1])&&k1<k;k1++);  
76             if(k1==k)  
77                 strcpy(citys[k++],s1);  
78             for(k2=0;strcmp(s2,citys[k2])&&k2<k;k2++);  
79             if(k2==k)  
80                 strcpy(citys[k++],s2);  
81             map[k1][k2]=map[k2][k1]=tons;  
82         }  
83         scanf("%s%s",s1,s2);  
84         for(from=0;strcmp(citys[from],s1);from++);  
85         for(to=0;strcmp(citys[to],s2);to++);  
86         run();  
87         printf("Scenario #%d
",t++);  
88         printf("%d tons

",ans);  
89     }  
90     return 0;  
91 }

当然了，优先队列的用法决不是仅仅提到的这些，各种应用还需要大家去发现，给道题大家可以练习一下hdu 2066
相信大家已经学到不少了，还有一点可以告诉大家，优先队列是启发式搜索的数据结构基础，希望好好理解，并逐步掌握其用法~
 加：失策啊，竟然忘了说优先队列的效率了，其时间复杂度为O(logn).n为队列中元素的个数，存取都需要消耗时间~

转自：http://www.cnblogs.com/luoxn28/p/5616101.html

http://www.cnblogs.com/heqinghui/archive/2013/07/30/3225407.html