堆基础解析及操作

基础

堆（heap）是一种满足特定条件的完全二叉树，主要可分为两种类型。

• 小顶堆（min heap）：任意节点的值 ≤ 其子节点的值。
• 大顶堆（max heap）：任意节点的值 ≥ 其子节点的值。

堆作为完全二叉树的一个特例，具有以下特性。

• 最底层节点靠左填充，其他层的节点都被填满。
• 我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。
• 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。

“二叉树”章节讲过，完全二叉树非常适合用数组来表示。由于堆正是一种完全二叉树，因此我们将采用数组来存储堆。

当使用数组表示二叉树时，元素代表节点值，索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。

操作

入堆

给定元素 val ，我们首先将其添加到堆底。添加之后，由于 val 可能大于堆中其他元素，堆的成立条件可能已被破坏，因此需要修复从插入节点到根节点的路径上的各个节点，这个操作被称为堆化（heapify）。

考虑从入堆节点开始，从底至顶执行堆化。比较插入节点与其父节点的值，如果插入节点更大，则将它们交换。

出堆

• 交换堆顶元素与堆底元素（交换根节点与最右叶节点）。
• 交换完成后，将堆底从列表中删除（注意，由于已经交换，因此实际上删除的是原来的堆顶元素）。
• 从根节点开始，从顶至底执行堆化。

“从顶至底堆化”的操作方向与“从底至顶堆化”相反，我们将根节点的值与其两个子节点的值进行比较，将最大的子节点与根节点交换。然后循环执行此操作，直到越过叶节点或遇到无须交换的节点时结束。

建堆

除了对每个元素执行入堆操作以外，可以采用直接遍历，自顶向下把原有数组直接堆化，由于叶子节点数量很多，实际操作次数（实际复杂度）是O(n)。

/* 构造方法，根据输入列表建堆 */
MaxHeap(List<Integer> nums) {
    // 将列表元素原封不动添加进堆
    maxHeap = new ArrayList<>(nums);
    // 堆化除叶节点以外的其他所有节点
    for (int i = parent(size() - 1); i >= 0; i--) {
        siftDown(i);
    }
}

看起来是nlogn的复杂度，实际上因为不同的层的操作次数是不一样的，每次堆化操作的复杂度并非都是O(logn)，最后经数学推导可知，复杂度为O(n)

特性

堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为 O(log⁡n) ，而建堆操作为 O(n) ，这些操作都非常高效。

Top-k问题

我们可以基于堆更加高效地解决 Top-k 问题，流程如图 8-8 所示。

1. 初始化一个小顶堆，其堆顶元素最小。
2. 先将数组的前 k 个元素依次入堆。
3. 从第 k+1 个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
4. 遍历完成后，堆中保存的就是最大的 k 个元素。

‍