[What]数据结构与算法 -> 堆

课程:王争 –> <数据结构与算法之美>

认识堆这种树。

实践代码位于github

概念

堆其实是一种特殊的树,当树满足以下两点时,它就是一个堆:

  • 完全二叉树
  • 每个节点的值都必须大于等于或小于等于其左右子节点的值。
    • 每个节点的值都大于等于其左右子节点的值时,称为 大顶堆
    • 每个节点的值都小于等于其左右子节点的值时,称为 小顶堆
heap_overview.jpg

操作

在进行节点的插入和删除操作时,必然需要保持堆的特性(堆化),这就涉及到要移动(交换)原来的节点。

倘若使用链式存储,则在节点移动(交换)时需要通过指针搜寻其父或子节点,操作效率不高。

若使用数组存储,则可以通过索引直接获取其父或子节点,操作效率较高。

  • 并且完全二叉树可以很好的利用数组存储空间,这真是太妙了!

插入

插入的节点从数组下标1处开始,在插入节点后需要遍历的与其父节点(i/2)进行比较,当不满足大小关系时则进行交换。

删除堆顶元素

删除堆顶元素(下标为1的值) 后,如果从堆顶遍历的与左右节点比较后交换,则 最终可能会破坏完全二叉树

解决办法是: 删除堆顶元素后,将堆 最后一个元素(数组中的最后下标元素) 放入堆顶,然后再进行遍历比较交换。

堆化的时间复杂度

一个包含n个节点的完全二叉树,树的高度不会超过 log2(n) ,由于其堆化的过程也是顺着节点路径进行比较, 所以一个节点堆化的时间复杂度也是O(logn), 那么n个节点的时间复杂度就是 O(nlogn).

使用堆对数组的元素进行排序

堆对应于以数组方式存储的完全二叉树,所以它可以对数组中的元素先进行建堆,再进行排序。

建堆

当数组中有n个元素(从索引1开始),那么对于完全二叉树而言,其 1 ~ n/2 索引处为所有的父节点。 在进行堆化时,从 索引 n/2 至 1 处倒叙的方式进行从上往下的堆化。

  • 之所以要倒叙,是因为对于每个元素的堆化都需要其下面的元素已经被堆化好了。

排序

  1. 将堆顶的元素和数组最后一个元素交换
  2. 将除开最后一个元素的数组进行堆化
  3. 重复步骤1,直到剩下一个元素。

应用

优先级队列

大顶堆或小顶堆中堆顶的元素比其所有子节点都要大或小,就是说它就是最大或最小的节点。

根据此特性就可以应用于优先级队列,比如每次插入一个数据到堆中,并从中取出最大的值:

  • 得到堆顶元素,并删除堆顶元素
  • 堆化以保证堆特性
  • 插入节点

求 Top K

为求得前K大的数据,需要如下操作:

  • 建立一个小顶堆
  • 从待取数据中取出一个值与小顶堆比较,如果数据比堆顶大则删除堆顶元素,并将其插入小顶堆中

最终这个小顶堆中便保留了前K大的数据, 再依照前面讲的排序过程依次排序即可。

当从n大的数组取出top k 数据时,其最大时间复杂度为 O(nlogk)

  • 遍历一次数组为O(n)
  • 每次堆化是 O(logk)

求中位数

对于静态数组求中位数,仅需要先排序再取索引为(n / 2)处数据即可。

对于动态数据,那就需要维护一个大顶堆和一个小顶堆,假设需要求 n 个数据中的中位数:

  • 倘若n为奇数,大顶堆存储 (n / 2 + 1)个数据,小顶堆存储 ( n / 2) 个数据
    • 若n为偶数,大小顶堆都存放 (n /2 )个数据
  • 大顶堆中的数据都小于小顶堆的数据,这样中位数就是大顶堆的堆顶元素了
  • 插入数据时:
    • 如果新加入的数据小于大顶堆的堆顶,则插入大顶堆
    • 如果新加入的数据大于小顶堆的堆顶,则插入小顶堆
  • 插入数据后,为了能让两个堆个数满足要求,需要将一个堆顶移动到另一个堆。
Last Updated 2019-05-10 五 07:32.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)