完全二叉堆(大小堆)及优先级队列

2017-05-11 12:56 阅读 1,998 次 评论 1 条

堆是继栈、队列以及二叉树之后又一个重要的数据结构,堆在底层也是没有自己的容器的,而是通过binary heap这种complete binary tree(完全二叉树)来实现的。下面就堆的实现原理及底层容器作以阐述和实现。

完全二叉堆

complete binary tree(完全二叉树),整棵树除了最底层的叶节点之外,是填满的,而最底层的叶节点由左至右不得有空隙,这样带来的好处是:我们可以利用array来储存所有的结点。

如上图所示,我们可以将完全二叉树的结点按照层序遍历的顺序储存在一个数组中,那么当完全二叉树中的某个结点位于array的i处时,其左子节点必位于2i+1处(i>=0),其右结点必位于array的2i+2处。这样我们就可以轻易的实现完全二叉树的存储。

若将结点v的编号(秩)记作i(v),则满足以下关系:

一个array和一组heap算法(用于插入元素、删除元素、取极值,将某一个数组数据排列成一个heap),array的缺点是无法动态改变大小,而heap却需要这样的功能,因此,以vector代替array是再好不过了。

堆存储在下标为0开始计数的数组中,因此在堆中给定小标为i的结点时:

①如果i=0: 结点i是根节点,没有双亲节点;否则结点i的双亲结点为结点(i-1)/2。
②如果2*i+1>n-1: 则结点i无左孩子,否则结点i的左孩子为结点2*i+1。
③如果2*i+2>n-1: 则结点i无右孩子,否则结点i的右孩子为结点2*i+2。

最大堆和最小堆

根据元素排列方式,heap可分为max-heap和min-heap两种,前者每个节点的键值(key)都大于或等于其子节点键值,后者的每个节点键值(key)都小于或等于其子节点键值。

因此,max-heap的最大值在根节点,并总是处于底层array或vector的头部。min-heap的最小值在根节点,总是位于底层array或vector的起头处。

以测试用例数组的{3,4,6,5,7,2}为例,其大小堆结构分别为:

源代码及注释

优先级队列

优先级队列的实现调用的是堆的方法。priority-queue带有权值观念,其内的元素并非依照被推入的次序排列,而是自动依照元素的权值进行排列。通过complete binary tree以vector为底层容器就可以实现底端加入元素,顶端取出元素的操作

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:完全二叉堆(大小堆)及优先级队列 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情