算法复习 – 堆 优先队列

本文是优先队列即二叉堆(heap)的整理,包括:

  • push
  • pop
  • 堆的创建及其他应用

优先队列

在多任务环境中,操作系统必须决定在若干进程中运行哪个进程。我们知道,有一些任务应当具有优先权,对这些特殊的应用似乎需要一类特殊的队列,称之为优先队列(priority queue)。

优先队列至少应该实现insert和deleteMin操作。

一些简单的实现如下:

  • 链表,插入队头O(1), 删除最小的元素则需要遍历链表O(n) 另一个方法是让链表保持在排序的状态,这使得插入代价O(n),而deleteMin只需要O(1)
  • BST:二叉查找树 对于两种操作平均时间都是O(logN),但可能导致树的不平衡,用平衡树又显得过于麻烦

故优先队列使用二叉堆(binary heap)来实现。

 

二叉堆

简介

如下图所示:

binary-heap

对于数组中任意位置i上的元素,左儿子在2i上,右儿子在2*i+1上,而父亲在i/2上。

对于堆,其最小元总在根上,并且任意的子树也应该是堆。(即任意结点应该小于它的后裔)

 

堆的基本操作

1.insert

为了插入一个元素,我们在下一个空闲位置创建一个空穴,并对其与父结点进行比较,进行上滤操作。

如图,插入14,将14与父结点31比较,小于父结点,故把父结点放入下面的位置,14不断的上移直到找到正确的位置。

binary-heap-insert

实现的代码如下,显然其复杂度为O(logN)

 

2.deleteMin

对于删除操作,把最后一个元素放在第一个位置,然后长度减一,相当于覆盖了原有的最小元素,然后对根结点进行下滤操作寻找合适的位置,来维护堆。如下图所示。

binary-heap-deleteMin

有一个陷阱是,将最后一个元素放在第一个位置后,原有的长度减少一,可能并没有右儿子结点。见上图的21.为此,我们需要进行判断。见下面的代码。

可以看出,删除操作的复杂度也为O(logN)

 

堆的其它操作

至于返回最小的(返回根array[1])和堆是否为空return currentSize ==0 我就不说了

1.decreaseKey(p,x)

该操作将减少p处元素的值。减少的幅度为x(x>0),这可能破坏堆的性质,因此需要进行上滤操作

2.increaseKey(p,x)

该操作将增加p处元素的值。增加的幅度为x(x>0),因此用下滤操作

3.remove(p)

该操作删除堆中位置p上的结点。首先执行decreaseKey(p,∞),然后在执行deleteMin来完成

4.bulidHeap

对于一个堆,我们可以通过N次连续的insert来完成,需要O(NlogN)操作来完成.下面要讲的是O(N)的建堆方法。

将N项以任意顺序放入树中,然后对每个有儿子结点的进行下滤操作来维护堆。可以证明,其总的复杂度为O(N)

binary-heap-delete

 

5.最大堆

最大堆和最小堆只需要改变一下比较的函数即可。最好用c++的重载运算符。

 

C++重载运算符比如,用这个比较的话<则其实是返回>的结果,即使用之前的代码即可实现最大堆。

 

下面是Poj的一道题的堆的解法。我并没有用重载运算符,所以都需要改运算符的符号<改大于啥的。

还有就是模仿STL的priority_queue,故insert和deleteMin操作对应的是push 和 pop

你可以自己实现一遍,加深理解。:)

http://poj.org/problem?id=1862

题解在我的CSDN http://blog.csdn.net/murmured/article/details/25476967

 

 

参考资料

  • 《数据结构与算法分析 C++描述》
本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > 算法复习 – 堆 优先队列
本文地址:https://www.hrwhisper.me/algorithm-heap-priority-queue/

打赏一杯咖啡钱呗

算法笔记 , , , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *