随笔 - 13  文章 - 36  trackbacks - 0
<2009年10月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(2)

随笔档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

                                                                                    优先级队列

                                                                                                   C++博客   Alex-Lee   2009-10-18
      
        上篇随笔谈到了堆结构的一个应用就是堆排序算法,虽然堆排序算法性能不错,但是比起快速排序算法还是有些差距。但是堆结构的另外一个应该就比较广泛了,就是优先级队列。
        优先级队列有3中操作:插入(O(lgn)),最大最小值(O(1)),删去最大最小值(O(lgn))。其算法性能很好,在优先级调度作业上应用比较广泛。基于优先级的调度算法中,基于堆结构的实现算法是一个比较好选择。在事件驱动的仿真器中也有应用。
       优先级队列算法实现:
1,数据结构:
1typedef 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 阅读(1202) 评论(3)  编辑 收藏 引用

FeedBack:
# re: 优先级队列 2009-10-18 18:00 凡客诚品网
构的另外一个应该就比较广泛了,就是优先级队列  回复  更多评论
  
# re: 优先级队列 2009-10-18 18:13 OwnWaterloo
删去最大最小值(O(1)) ???

删除操作不包括shift? 不shift的话,剩下的就不是堆了。
删除操作包括shift,复杂度就是对数。


  回复  更多评论
  
# re: 优先级队列 2009-10-18 18:25 Alex-Lee
@OwnWaterloo
写错了,呵呵,删除操作复杂度是O(lgn),这就改过来。谢谢。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理