数据结构与算法 / 系统课时

堆化操作

堆化操作

堆化负责在局部顺序被破坏后恢复堆性质。完成本课后,你将能独立实现向下堆化与向上堆化,判断它们各自适用的场景,并理解为什么一次堆化只需沿树高移动,因此时间复杂度为 O(log⁡n)O(\log n)。

学习目标

  • 理解向下堆化与向上堆化的触发条件和移动方向
  • 使用数组下标关系实现最大堆的两种堆化操作
  • 分析堆化的边界条件、正确性与时间复杂度

堆化解决什么问题

最大堆要求任意父节点的值都不小于其子节点。插入新元素、删除堆顶或修改节点值后,通常只有一条祖先链或后代链可能失序,因此无需重新检查整个数组,只要沿受影响路径交换元素即可。

向下堆化用于“父节点可能过小”的场景,例如删除堆顶后把最后一个元素放到根节点;向上堆化用于“子节点可能过大”的场景,例如在数组末尾插入新元素。

最大堆中向下与向上堆化的路径

核心原理

使用从下标 0 开始的数组存储完全二叉树时,节点 i 的关系如下:

  • 父节点下标为 (i - 1) / 2,只对 i > 0 有效
  • 左子节点下标为 2 * i + 1
  • 右子节点下标为 2 * i + 2
  • 子节点下标不小于 size 时,表示该子节点不存在

向下堆化每轮先在当前节点、左子节点和右子节点中选择最大值。如果最大值仍是当前节点,堆性质已经恢复;否则交换后继续检查被交换到的下一层。向上堆化则比较当前节点与父节点,只要当前值更大就交换并继续向根移动。

操作 常见触发场景 移动方向 停止条件
向下堆化 删除堆顶、根节点变小 从父节点到子节点 当前节点不小于两个子节点
向上堆化 尾部插入、节点值变大 从子节点到父节点 当前节点不大于父节点或到达根节点

完全二叉树的高度为 ⌊log⁡2n⌋\lfloor \log_2 n \rfloor。一次堆化最多沿一条根到叶或叶到根的路径移动,因此时间复杂度为 O(log⁡n)O(\log n),额外空间复杂度为 O(1)O(1)。

完整可运行示例

下面的 Java 17 程序先对根节点执行向下堆化,再把新元素追加到数组末尾并执行向上堆化。两个方法都使用循环实现,避免递归调用带来的额外栈空间。

java
import java.util.Arrays;

public class HeapifyDemo {

    public static void siftDown(int[] heap, int size, int index) {
        while (true) {
            int largest = index;
            int left = 2 * index + 1;
            int right = 2 * index + 2;

            // 每轮在当前节点和两个子节点中选择最大值
            if (left < size && heap[left] > heap[largest]) {
                largest = left;
            }
            if (right < size && heap[right] > heap[largest]) {
                largest = right;
            }

            if (largest == index) {
                return;
            }

            swap(heap, index, largest);
            index = largest;
        }
    }

    public static void siftUp(int[] heap, int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[parent] >= heap[index]) {
                return;
            }

            swap(heap, parent, index);
            index = parent;
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] heap = {3, 10, 8, 7, 6, 5};
        siftDown(heap, heap.length, 0);
        System.out.println("向下堆化: " + Arrays.toString(heap));

        int[] expanded = Arrays.copyOf(heap, heap.length + 1);
        expanded[expanded.length - 1] = 12;
        siftUp(expanded, expanded.length - 1);
        System.out.println("向上堆化: " + Arrays.toString(expanded));
    }
}

运行命令:

bash
javac HeapifyDemo.java
java HeapifyDemo

预期输出:

text
向下堆化: [10, 7, 8, 3, 6, 5]
向上堆化: [12, 7, 10, 3, 6, 5, 8]

边界与常见错误

当 size 为 0 或 1 时,不需要堆化。调用向下堆化前还应保证 index 位于有效区间;调用向上堆化时,新元素通常位于当前堆的最后一个有效位置。

常见错误是向下堆化时只与左子节点比较。右子节点可能更大,如果先和左子节点交换,就可能把更大的右子节点留在父节点下方,导致最大堆仍不合法。另一个错误是交换一次后立即结束;被交换下去的元素还可能继续小于下一层子节点,因此必须更新 index 并继续循环。

调试时可在每次交换后打印数组,并检查参与交换的下标。若只想验证最终结果,可遍历所有非叶节点,确认 heap[parent] >= heap[left],并在右子节点存在时确认 heap[parent] >= heap[right]。

本课练习

  1. 将示例改为最小堆,使父节点始终不大于子节点。分别调整比较条件,并用数组 [9, 4, 7, 1, 3] 验证结果。
  2. 编写 isMaxHeap(int[] heap, int size),遍历所有非叶节点并返回堆是否合法。验收条件是合法最大堆返回 true,任一父子关系违规时返回 false。
  3. 增加 increaseKey(int[] heap, int index, int newValue)。要求拒绝比原值更小的新值,并通过向上堆化恢复最大堆。

本课总结

  • 堆化只修复一条可能失序的路径,不需要重建整个堆
  • 向下堆化选择较大的子节点,向上堆化持续比较父节点
  • 两种操作最多移动一个树高,时间复杂度均为 O(log⁡n)O(\log n)

下一课预告

下一课将学习“建堆与堆排序”,先用自底向上的方式在线性时间内建立最大堆,再通过反复交换堆顶完成原地升序排序。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

堆化操作

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通