heapify

调整堆 的过程，让某个节点为根的子树重新满足堆的性质。

在某些情况下，我们希望使用一个列表的所有元素来构建一个堆，有两种构建方式：

• 用入堆操作建堆

  • 把一个空堆当起点，把数组里的元素一个一个放进去。

  • 每次放一个元素时，从底往上“调整”（堆化）。

  • 总共要放 $n$ 个元素，每次调整最坏 $O(\log n)$，所以总复杂度 $O(n\log n)$。

• 直接倒序堆化建堆

  • 先把所有元素直接放进数组里（不管堆规则）。

  • 从最后一个非叶子节点开始，依次往前，每个节点“从顶往下堆化”。

  • 因为叶子节点不用堆化，且底层节点数量最多、但高度很低，实际计算下来，整个过程的总复杂度是 $O(n)$。

若已有堆，有两种堆化方式：

• 从底到顶堆化（sift up / percolate up）

  • 场景：插入新元素时。

  • 步骤：把新元素先放到堆的最后一个位置，然后不断和“父节点”比较、交换，直到满足堆的性质。

  • 方向：子节点 → 父节点。

  • 时间复杂度：$O(\log n)$（最多上升到根）。

• 从顶到底堆化（sift down / percolate down）

  • 场景：删除堆顶元素、或建堆时。

  • 步骤：把“顶上的元素”往下放，不断和“左右子节点”比较、交换，直到满足堆的性质。

  • 方向：父节点 → 子节点。

  • 时间复杂度：$O(\log n)$（最多下降到叶子）。