優先級隊列
C++博客 Alex-Lee 2009-10-18
上篇隨筆談到了堆結構的一個應用就是堆排序算法，雖然堆排序算法性能不錯，但是比起快速排序算法還是有些差距。但是堆結構的另外一個應該就比較廣泛了，就是優先級隊列。
優先級隊列有3中操作：插入(O(lgn))，最大最小值(O(1)),刪去最大最小值(
O(lgn))。其算法性能很好，在優先級調度作業上應用比較廣泛。基于優先級的調度算法中，基于堆結構的實現算法是一個比較好選擇。在事件驅動的仿真器中也有應用。
優先級隊列算法實現：
1，數據結構：
1
typedef struct int_array
2
{
3
int *pa;//數組，對于任意類型的數據，可以使用char *pc,int typelen實現。
4 int array_size;//數組元素數量
5 int capacity;//緩存大小
6
} INT_ARRAY;//有點類似于vector
2，heap_insert
1#define PARENT(i) i/2
2
3
4void heap_insert(INT_ARRAY *pia,int key)
5{
6 int *pa1,i;
7 if (pia->array_size == pia->capacity)
8
{
9 pa1 = (int*)malloc(pia->capacity *2 * sizeof(int));
10 for (i = 0;i<pia->array_size;++i)
11 {
12 pa1[i] = pia->pa[i];
13
}
14 free(pia->pa);
15 pia->pa = pa1;
16 pia->capacity = 2 * pia->capacity;
17 }
18 pia->array_size ++;
19 i = pia->array_size - 1;
20 while (i > 0 && pia->pa[PARENT(i)] <key)
21 {//key作為孩子結點，與父節點比較
22 pia->pa[i] = pia->pa[PARENT(i)];
23 i = PARENT(i);
24 }
25 pia->pa[i] = key;
26}
3,heap_max
1int heap_max(INT_ARRAY *pia)
2{
3 return pia->pa[0];
4}
4,heap_exact_max
1int heap_exact_max(INT_ARRAY *pia)
2{
3 int max;
4
5 max = pia->pa[0];
6 pia->pa[0] = pia->pa[pia->array_size -1];
7 pia->array_size --;
8 heap_ify(pia,pia->array_size,0);
9 return max;
10}
5,實現代碼
堆算法
6,參考《算法導論（中文版）》潘金貴
ps,今天下午編輯更新隨便的時候，發現提交后，該隨筆的數據丟失厲害，基本上數據丟得差不多沒了，這是重新寫了一遍。可能是網速慢引起的。
posted on 2009-10-18 18:49
Alex-Lee 閱讀(1271)
評論(3) 編輯 收藏 引用