例题

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

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

插入操作

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

)

移除操作

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

完整代码实现

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
     
          3 #include
      
           4 #include
       
            5 #include
        
             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
         
          a.x;//最小值优先   23     }   24 };   25 struct number2{   26     int x;   27     bool operator < (const number2 &a) const {   28         return x
          

que;//采用默认优先级构造队列 37 38 priority_queue

,cmp1>que1;//最小值优先 39 priority_queue

,cmp2>que2;//最大值优先 40 41 priority_queue

,greater

>que3;//注意“>>”会被认为错误， 42 //这是右移运算符，所以这里用空格号隔开 43 priority_queue

,less

>que4;////最大值优先 44 45 priority_queue

que5; 46 priority_queue

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("采用默认优先关系:\n(priority_queue

que;)\n"); 63 printf("Queue 0:\n"); 64 while(!que.empty()){ 65 printf("%3d",que.top()); 66 que.pop(); 67 } 68 puts(""); 69 puts(""); 70 71 printf("采用结构体自定义优先级方式一:\n(priority_queue

,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

,greater

/less

>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

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

que;) 118 Queue 0: 119 91 83 72 56 47 36 22 14 10 7 3 120 121 采用结构体自定义优先级方式一: 122 (priority_queue

,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

,greater

/less

>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

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 */