数据结构之堆

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
605
文章
12
评论
2019年4月27日11:25:27 评论

一、堆

堆是一种数据结构,通常通常所说的堆即二叉堆。二叉堆是一个数组,可以被看成一个完全二叉树,如下图所示:

数据结构之堆

他在数组中的表现形式为:

数据结构之堆

通过数组很容易得到每个父节点和其子节点的关系,假设数组的起始下标为0,那么有:

因此可以直接在程序中定义:

二、最大堆和最小堆

堆有最大堆和最小堆之分,在最大堆中,除了根节点以外的所有节点i都要满足:A[PARENT[i]] >= A[i],所有的子节点的值不会超过其父节点的值。因此,在最大堆中,最大的元素存放在根节点中。

而最小堆和最大堆相反,除了根节点以外的所有节点i都要满足:A[PARENT[i]] <= A[i], 所有子节点的值都大于等于其根节点的值。因此,最小堆中根节点的元素是最小的。

在堆排序算法中,使用的是最大堆,最小堆通常用于构造优先级队列。

以最大堆为例,其包含的操作为:

  • MAX_HEAPIFY:用来维护一个最大堆。
  • BUILD_MAX_HEAP:从一堆无序的数组中构造出一个最大堆。
  • HEAPSORT:执行一次堆排序过程。

三、最大堆

3.1 维护最大堆

把一个堆构造成最大堆的流程:

  1. 从A[i], A[LEFT[i]], A[RIGHT[i]]中选出最小的,保存其下标largest。
  2. 如果largest不等于i,交换A[i]和A[largest]。

以下图为例,当前堆中4处于一个非正确的位置:

数据结构之堆

首先把4和其儿子中最大的14交换,得到以下堆:

数据结构之堆

交换后4依旧不是最小的元素,继续交换48

数据结构之堆

4当前已经是叶子节点了,此时对4的最大堆化操作就完成了。并且此时的堆也就是一个最大堆。

不难看出:对一个高度为h的树来说,这个操作的时间复杂度为O(h)

对应的c代码:

3.2 建堆

建堆的过程实际上是执行多次MAX_HEAPIFY,我们只需对2/n以内的元素都执行MAX_HEAPIFY操作即可完成一个最大堆的构建。

因为[n/2, n)之间的元素都是叶子节点,所以无需对它们进行转换操作。

要注意的是建堆必须从下往上,否则可能出现堆只是局部有效,对全局而言并非有效:

数据结构之堆

以上图为例,如果从上到下建堆,在调整完4的位置之后,14被放在了树根。而实际上被放在树根的应该是16,因为接下来就不会调整14了,它的位置就永远不对,这个堆也就不是一个符合要求的堆。

代码:

四、堆排序

参考:排序算法之堆排序

马谦马谦马谦
  • 本文由 发表于 2019年4月27日11:25:27
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/heap.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: