数据结构与算法之美-堆

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

如何构建一个堆

我们知道完全二叉树适合用数组存储，所以堆比较适合用数组实现。如下图所示，以下标 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 的元素进行堆化。文字表达比较难懂，可以结合下图进行理解

排序

建堆结束后，数组中的元素已经是按照大顶堆的特性来组织的了。数组中的第一个元素就是堆顶，也是最大的元素。我们把它与最后一个元素交换，那最大元素就放到了下标为 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%的结果，调整大小顶堆的数据量占比例即可。