優(yōu)先級隊(duì)列
C++博客 Alex-Lee 2009-10-18
上篇隨筆談到了堆結(jié)構(gòu)的一個(gè)應(yīng)用就是堆排序算法，雖然堆排序算法性能不錯(cuò)，但是比起快速排序算法還是有些差距。但是堆結(jié)構(gòu)的另外一個(gè)應(yīng)該就比較廣泛了，就是優(yōu)先級隊(duì)列。
優(yōu)先級隊(duì)列有3中操作：插入(O(lgn))，最大最小值(O(1)),刪去最大最小值(
O(lgn))。其算法性能很好，在優(yōu)先級調(diào)度作業(yè)上應(yīng)用比較廣泛。基于優(yōu)先級的調(diào)度算法中，基于堆結(jié)構(gòu)的實(shí)現(xiàn)算法是一個(gè)比較好選擇。在事件驅(qū)動的仿真器中也有應(yīng)用。
優(yōu)先級隊(duì)列算法實(shí)現(xiàn)：
1，數(shù)據(jù)結(jié)構(gòu)：
1
typedef struct int_array
2
{
3
int *pa;//數(shù)組，對于任意類型的數(shù)據(jù)，可以使用char *pc,int typelen實(shí)現(xiàn)。
4 int array_size;//數(shù)組元素?cái)?shù)量
5 int capacity;//緩存大小
6
} INT_ARRAY;//有點(diǎn)類似于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作為孩子結(jié)點(diǎn)，與父節(jié)點(diǎn)比較
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,實(shí)現(xiàn)代碼
堆算法
6,參考《算法導(dǎo)論（中文版）》潘金貴
ps,今天下午編輯更新隨便的時(shí)候，發(fā)現(xiàn)提交后，該隨筆的數(shù)據(jù)丟失厲害，基本上數(shù)據(jù)丟得差不多沒了，這是重新寫了一遍。可能是網(wǎng)速慢引起的。
posted on 2009-10-18 18:49
Alex-Lee 閱讀(1259)
評論(3) 編輯 收藏 引用