优先级队列
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 阅读(1255)
评论(3) 编辑 收藏 引用