当前位置:   article > 正文

数据结构-堆(Heap)、堆排序_heap排序

heap排序

一、堆(Heap)是一种特殊的树

  • 堆是一个完全二叉树(除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列);
  • 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。

对于每个节点的值都大于等于子树中每个节点值的堆,我们叫做“大顶堆”
对于每个节点的值都小于等于子树中每个节点值的堆,我们叫做“小顶堆”

二、堆的存储

完全二叉树适合用数组存储,所以堆也适合用数组存储。

因此可得,数组下标是 i 的元素,它的父节点以及左右子节点的位置分别是:
parent(i) = floor((i - 1)/2)【向下取整】
left(i) = 2i + 1
right(i) = 2i + 2

三、堆中比较重要的两个操作

堆中比较重要的两个操作是插入一个数据和删除堆顶元素。这两个操作都要用到堆化(heapify)。
1)插入一个数据的时候,我们把新插入的数据放到数组的最后,然后从下往上堆化
在这里插入图片描述

原本存储[ 10, 7, 2, 5, 1 ],插入16后[ 10, 7, 2, 5, 1,16 ]
  • 1

在数组末尾插入新数据16后不满足堆,要进行堆化(交换),向上堆化。16与2比较交换,16继续向上和10比较交换,最后蓝色状态满足堆,插入结束。

2)删除堆顶数据的时候,我们把数组中的最后一个元素放到堆顶,然后从上往下堆化。这两个操作时间复杂度都是 O(logn)。

原本存储[ 10, 7, 2, 5, 1 ],删除10后[ 1, 7, 2, 5]
  • 1

删除堆顶元素,将数组末尾的数交换上来,但是目前不满足堆的特点了,所以也要进行堆化(交换),向下堆化。然后比较1和7(7和2选择较大的放到堆顶,所以此处选择1和7交换),继续堆化,1和5交换,直到该节点没有任何子节点或者它比两个子节点都要大,即图中灰色状态满足堆,结束。在这里插入图片描述

小结:完全二叉树的高度为log2n ,因此,堆的删除、插入元素时间复杂度为 O(logn)。

四、堆排序

堆排序包括建堆和排序两个操作,建堆和排序。

  1. 建堆
    借助在堆中插入一个元素的思路。尽管数组中包含 n 个数据,假设起初堆中只包含一个数据,然后依次将n-1个数据依次插入到堆中,这样,建堆结束之后,数组中的数据已经是按照大顶堆的特性来组织的。时间复杂度是 O(n)。
  2. 排序
    对于完全二叉树来说,下标从 n/2​ 到 n-1 的节点都是叶子节点,如图,3214为叶子节点,存储下标从8/2到7。因为叶子节点不需要堆化,每个节点堆化的时间复杂度是 O(logn),那 n/2​个节点堆化的总时间复杂度就是 O(nlogn) 。

小结:堆排序包括建堆和排序两个操作,建堆和排序。建堆过程的时间复杂度是 O(n),排序过程的时间复杂度是 O(nlogn),所以,堆排序整体的时间复杂度是 O(nlogn)。

注意:堆排序和快速排序都是 O(nlogn)的算法,甚至堆排序更稳定,但是实际应用快速排序会比较多:原因是对堆顶节点进行堆化,会依次访问数组下标是 0,1,3 的元素,而不是像快速排序那样,局部顺序访问,所以,这样对 CPU 缓存是不友好的。另外堆排序比快速排序交换次数多,可以通过程序打印比较次数验证。

五、堆的典型应用

1、堆排序
2、优先级队列
3、求动态集合中位数
4、求第K大元素
5、cpu相应大于99%的应用等等

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/681462
推荐阅读
相关标签
  

闽ICP备14008679号