优先队列,其实我一直不愿承认“优先队列”是一种“队列”,现实世界的队列(比如排队)告诉我们,队列最明显的性质就是先进先出。而优先队列,似乎跟这个规则没什么关系,出队的早晚跟进队的顺序基本没关系,而是看谁更有“特权”。我排队排了一大早上,你小子刚来凭什么比我先买到早餐?这简直太不公平啦!
似乎又不是这么回事,一般的队列也是有“特权”的,它的特权是时间,谁进队的时间久谁就更有特权;而优先队列的“特权”是我们规定的另一种东西。
不去纠结这个问题了,我们来看看优先队列吧。
这里用堆实现优先队列,只讨论入队(EnQueue())和出队(Dequeue()),都具有O(logN)的时间复杂度。其实还有一个很重要的操作:改变队列中某个元素的权值,这里就不讨论了。

关于堆的操作可以先参阅我前面的文章《堆排序》(http://www.cppblog.com/hoolee/archive/2012/07/16/183700.html
初始化优先队列的过程就是建立堆的过程,维护队列的过程就是维护堆的过程。
初始化队列:
经过n/2次筛选(由f()函数实现)即可,这里不再赘述。
入队:
入队操作先将该元素num加到堆的末尾,为了保持堆(大顶堆)的性质,需要将num不断与父节点比较,如果num比父节点大就交换它们。
void EnQueue(int *a, int *r, int num)
    a[]是存放堆的数组
    *r为队列的长度,指向堆中的最后一个元素
    num为要加入队列的数字

出队:
出队的操作很简单,直接将堆顶元素弹出即可,不过为了维护堆的性质,我们还要进行一次“筛选”。下面的代码是先将堆中最后一个元素赋给堆顶元素,然后进行一次筛选。(另一种方式是直接将堆顶元素修改为MIN,然后进行一次筛选)




 

posted on 2012-07-20 10:36 小鼠标 阅读(3291) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜