优先队列,其实我一直不愿承认“优先队列”是一种“队列”,现实世界的队列(比如排队)告诉我们,队列最明显的性质就是先进先出。而优先队列,似乎跟这个规则没什么关系,出队的早晚跟进队的顺序基本没关系,而是看谁更有“特权”。我排队排了一大早上,你小子刚来凭什么比我先买到早餐?这简直太不公平啦!似乎又不是这么回事,一般的队列也是有“特权”的,它的特权是时间,谁进队的时间久谁就更有特权;而优先队列的“特权”是我们规定的另一种东西。不去纠结这个问题了,我们来看看优先队列吧。这里用堆实现优先队列,只讨论入队(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,然后进行一次筛选)