操作系统内核作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方 式来进行调度；
如果最小键值元素拥有最高的优先级，那么这种优先队列叫作升序优先队列（即总是先删除最小 的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作降序优先队列 （即总是先删除最大的元素）；由于这两种类型是完全对称的，所以只需要关注其中一种，如升 序优先队列.
优先队列算法实现：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #define DEFAULT_CAPCITY 128
6 #define isLess(a,b) (a<b)
7
8 typedef int DataType;
9
10 typedef struct _PriorityQueue
11 {
12 DataType *arr; //存储堆元素的数组
13 int size; //当前已存储的元素个数
14 int capacity; //当前存储的容量
15 }PriorityQueue;
16
17 bool init(PriorityQueue &pq, int *orginal, int size);
18 bool push(PriorityQueue &pq, DataType value);
19 bool pop(PriorityQueue &pq, DataType &value);
20 bool isEmpty(PriorityQueue &pq);
21 bool isFull(PriorityQueue &pq);
22 void destroy(PriorityQueue &pq);
23 static void build(PriorityQueue &pq);
24 static void adjustDown(PriorityQueue &pq, int index);
25 static void adjustUp(PriorityQueue &pq, int index);
26
27 /*初始化优先队列*/
28 bool init(PriorityQueue &pq, DataType *orginal, int size)
29 {
30 int capacity = DEFAULT_CAPCITY>size ? DEFAULT_CAPCITY : size;
31 pq.arr = new DataType[capacity];
32 if (!pq.arr) return false;
33 pq.capacity = capacity;
34 pq.size = 0;
35
36 //如果存在原始数据则构建最大堆
37 if(size > 0)
38 {
39 //方式一: 直接调整所有元素
40 memcpy(pq.arr, orginal, size*sizeof(int));
41 pq.size = size;
42 //建堆
43 build(pq);
44 }
45 return true;
46 }
47
48 /*销毁优先级队列*/
49 void destroy(PriorityQueue &pq)
50 {
51 if(pq.arr) delete[] pq.arr;
52 }
53
54 /*优先队列是否为空*/
55 bool isEmpty(PriorityQueue &pq)
56 {
57 if(pq.size<1) return true;
58 return false;
59 }
60
61 /*优先队列是否为满*/
62 bool isFull(PriorityQueue &pq)
63 {
64 if(pq.size<pq.capacity) return false;
65 return true;
66 }
67
68 int size(PriorityQueue &pq)
69 {
70 return pq.size;
71 }
72
73 /* 从最后一个父节点(size/2-1 的位置)逐个往前调整所有父节点（直到根节
74 点）, 确保每一个父节点都是一个最大堆，最后整体上形成一个最大堆 */
75 void build(PriorityQueue &pq)
76 {
77 int i;
78 for (i = pq.size / 2 - 1; i >= 0; i--)
79 {
80 adjustDown(pq, i);
81 }
82 }
83
84 /*将当前的节点和子节点调整成最大堆*/
85 void adjustDown(PriorityQueue &pq, int index)
86 {
87 DataType cur = pq.arr[index]; //当前待调整的节点
88 int parent, child;
89
90 /*判断否存在大于当前节点子节点，如果不存在 ，则堆本身是平衡的，不需要调整；
91 如果存在，则将最大的子节点与之交换，交换后，如果这个子节点还有子节点，则要继续
92 按照同样的步骤对这个子节点进行调整*/
93 for (parent = index; (parent * 2 + 1)<pq.size; parent = child)
94 {
95 child = parent * 2 + 1;
96
97 //取两个子节点中的最大的节点
98 if (((child + 1)<pq.size) && isLess(pq.arr[child], pq.arr[child + 1]))
99 {
100 child++;
101 }
102
103 //判断最大的节点是否大于当前的父节点
104 if (isLess(pq.arr[child], cur))
105 {
106 //不大于，则不需要调整，跳出循环
107 break;
108 }
109 else
110 {
111 //大于当前的父节点，进行交换，然后从子节点位置继续向下调整
112 pq.arr[parent] = pq.arr[child];
113 pq.arr[child] = cur;
114 }
115 }
116 }
117
118 /*将当前的节点和父节点调整成最大堆*/
119 void adjustUp(PriorityQueue &pq, int index)
120 {
121 if(index<0 || index >= pq.size)
122 {
123 //大于堆的最大值直接 return
124 return;
125 }
126 while(index>0)
127 {
128 DataType temp = pq.arr[index];
129 int parent = (index - 1) / 2;
130 if(parent >= 0)
131 {
132 //如果索引没有出界就执行想要的操作
133 if( isLess(pq.arr[parent], temp) )
134 {
135 pq.arr[index] = pq.arr[parent];
136 pq.arr[parent] = temp;
137 index = parent;
138 }
139 else
140 {
141 //如果已经比父亲小 直接结束循环
142 break;
143 }
144 }
145 else
146 {
147 //越界结束循环
148 break;
149 }
150 }
151 }
152
153 /* 删除优先队列中最大的节点，并获得节点的值*/
154 bool pop(PriorityQueue &pq, DataType &value)
155 {
156 if (isEmpty(pq)) return false;
157 value = pq.arr[0];
158 pq.arr[0] = pq.arr[--pq.size];
159
160 //heap.arr[0] = heap.arr[heap.size-1];
161 //heap.size--;
162 adjustDown(pq, 0); // 向下执行堆调整
163 return true;
164 }
165
166 /*优先队列中插入节点*/
167 bool push(PriorityQueue &pq, DataType value)
168 {
169 if (isFull(pq))
170 {
171 fprintf(stderr, "优先队列空间耗尽！\n");
172 return false;
173 }
174 int index = pq.size;
175 pq.arr[pq.size++] = value;
176 adjustUp(pq, index);
177 return true;
178 }
179
180 int main(void)
181 {
182 PriorityQueue pq;
183 int task[] = { 1, 2, 3, 87, 93, 82, 92, 86, 95 };
184 int i = 0;
185
186 if(!init(pq, task, sizeof(task)/sizeof(task[0])))
187 {
188 fprintf(stderr, "初始化优先队列失败！\n");
189 exit(-1);
190 }
191
192 for (i = 0; i<pq.size; i++)
193 {
194 printf("the %dth task:%d\n", i, pq.arr[i]);
195 }
196
197 //堆中插入优先级为 88 的任务
198 push(pq, 88);//堆中元素出列
199 printf("按照优先级出列：\n");
200 DataType value;
201
202 while( pop(pq, value))
203 {
204 printf(" %d\n", value);
205 }
206 destroy(pq);
207
208 system("pause");
209 return 0;
210 }