原地堆化技巧

将数组以 \(O(n)\) 的时间复杂度和 \(O(1)\) 的空间复杂度构造为堆的 trick。

想象我们把数组随意地填充进一棵完全二叉树（尚不满足堆的性质），然后通过交换节点等操作把二叉树变成堆。因为完全二叉树的节点个数性质，我们直接从 \(\dfrac{n}{2}\) 到 \(1\) 倒序遍历（相当于从下到上遍历非叶子节点），对每一个节点做下沉操作（递归地与子树节点交换使满足堆的性质）。

代码如下：

void heapify(int[] h) { // 倒序遍历——从下往上遍历非叶子节点
    for (int i = h.length / 2 - 1; i >= 0; i--)  sink(h, i);
}
void sink(int[] h, int i) {
    int n = h.length;
    while (2 * i + 1 < n) {
        int j = 2 * i + 1; // 左儿子（因为起始下标为0所以+1）
        if (j + 1 < n && h[j + 1] > h[j]) j++; // 跟左右儿子中较大的交换
        if (h[i] >= h[j])  break; // 无法交换，递归结束
        swap(h, i, j), i = j; // 交换后继续向下递归
    }
}

THE END