数据结构与算法之美-堆

数据结构与算法之美-堆

堆是一个完全二叉树,每个节点的值都大于等于(或小于等于)其子节点的值。父节点值较大的称为大顶堆,父节点值较小的称为小顶堆。

如何构建一个堆

我们知道完全二叉树适合用数组存储,所以堆比较适合用数组实现。如下图所示,以下标 i 定位一个节点,则其左子节点下标为 $2i$ ,右子节点下标为 $2i+1$,父节点下标为 $i/2$。
堆结构

插入元素(大顶堆)

如果堆未满可以将新元素放到堆的最后,即数组的第一个空位置。这时的数据结构可能就不满足堆的特性了,这个时候我们就需要进行调整,调整过程就称为 堆化。我们可以将新插入的元素与其父节点进行比较,如果节点值比父节点大则进行交换,然后继续与新的父节点进行比较,直到节点值小于等于父节点或不存在父节点(到达堆顶)。

删除堆顶元素(大顶堆)

当堆已满且要插入的元素小于堆顶元素,此时就得先删除堆顶元素,然后再插入新元素。对于删除堆顶元素,我们可以将堆内最后一个元素放到堆顶,然后从堆顶开始从上往下进行堆化,直到父节点大于等于子节点。

我们知道,一个包含 n 个节点的完全二叉树,树的高度不会超过 $log_2^n$,堆化的过程是顺着节点所在路径比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就是O($log^n$) 。插入数据和删除堆顶元素的主要逻辑就是堆化,所以,往堆中插入一个元素和删除堆顶元素的时间复杂度都是O($log^n$)。

堆排序

借助于堆这种数据结构实现的排序算法,就叫作堆排序。这种排序算法的时间复杂度非常稳定,是O($n\log^n$),并且它还是原地排序算法。堆排序的过程大致分解成两个大的步骤,建堆和排序。

建堆

首先将数组原地建成一个堆。所谓“原地”就是,不借助另一个数组,就在原数组上操作。

建堆的思路有两种,第一种借助前面说的插入元素的方式。尽管数组中包含 n 个数据,但我们可以假设堆中一开始只有一个元素,即数组下标为1的元素,然后我们依次将数组下标从 2 至 n 的 n-1 个元素依次插入堆中,这样我们就将包含 n 个数据的数组组织成了一个堆。这种思路是按数组从前往后遍历,从下往上进行堆化完成的建堆过程。

第二种思路与这个完全相反,它是按数组从后往前遍历,从上往下进行堆化完成的建堆过程。具体操作:从第一个非叶子节点开始,从上往下进行堆化,保证以当前节点为根节点的子完全二叉树满足堆的特性。由于最后一个节点的下标为 n, 其父节点即为第一个非叶子节点,下标为 n/2,所以第二种思路需要对数组下标为 n/2 到 1 的元素进行堆化。文字表达比较难懂,可以结合下图进行理解
建堆-1
建堆-2

排序

建堆结束后,数组中的元素已经是按照大顶堆的特性来组织的了。数组中的第一个元素就是堆顶,也是最大的元素。我们把它与最后一个元素交换,那最大元素就放到了下标为 n 的位置。

这个过程有点像前面讲的“删除堆顶元素”的操作,当堆顶元素移除后,我们将下标为 n 的元素放到堆顶。然后再通过堆化的方法,将剩下的 n-1 个元素重新构建成堆。然后我们再取堆顶元素与下标为 n-1 的元素就行交换,再重新建堆。一直重复这个过程,直到最后堆中只剩下一个下标为 1 的元素,排序工作就完成了。

建堆的时间复杂度为O(n),排序的时间复杂度为O($nlog^n$) ,所以堆排序算法的时间复杂度为O($nlog^n$) 。点击这里查看代码实现。

堆的应用

  • 优先级队列,Java中的PriorityQueue。
  • 求Top K问题,求前Top K大的元素,用小顶堆。求前Top K小的元素,用大顶堆。
  • 求中位数,利用两个堆(一个小顶堆,一个大顶堆),元素总数n为奇数则小顶堆存储前 n/2 + 1 个元素,大顶堆存储后 n/2 个元素。n为偶数则小顶堆存储前 n/2 个元素,大顶堆存储后 n/2 个元素。当要插入的新元素的值大于等于大顶堆堆顶元素的值时插入大顶堆,否则插入小顶堆。然后通过大小顶堆之间迁移数据保证数据的平衡性。当要获取中位数时取小顶堆堆顶元素即可。
  • 求第百分之多少的结果,属于求中位数问题的变形,求中位数即求第50%的结果,调整大小顶堆的数据量占比例即可。