数据结构与算法 / 系统课时
堆化操作
堆化操作
堆化负责在局部顺序被破坏后恢复堆性质。完成本课后,你将能独立实现向下堆化与向上堆化,判断它们各自适用的场景,并理解为什么一次堆化只需沿树高移动,因此时间复杂度为 。
学习目标
- 理解向下堆化与向上堆化的触发条件和移动方向
- 使用数组下标关系实现最大堆的两种堆化操作
- 分析堆化的边界条件、正确性与时间复杂度
堆化解决什么问题
最大堆要求任意父节点的值都不小于其子节点。插入新元素、删除堆顶或修改节点值后,通常只有一条祖先链或后代链可能失序,因此无需重新检查整个数组,只要沿受影响路径交换元素即可。
向下堆化用于“父节点可能过小”的场景,例如删除堆顶后把最后一个元素放到根节点;向上堆化用于“子节点可能过大”的场景,例如在数组末尾插入新元素。

核心原理
使用从下标 0 开始的数组存储完全二叉树时,节点 i 的关系如下:
- 父节点下标为
(i - 1) / 2,只对i > 0有效 - 左子节点下标为
2 * i + 1 - 右子节点下标为
2 * i + 2 - 子节点下标不小于
size时,表示该子节点不存在
向下堆化每轮先在当前节点、左子节点和右子节点中选择最大值。如果最大值仍是当前节点,堆性质已经恢复;否则交换后继续检查被交换到的下一层。向上堆化则比较当前节点与父节点,只要当前值更大就交换并继续向根移动。
| 操作 | 常见触发场景 | 移动方向 | 停止条件 |
|---|---|---|---|
| 向下堆化 | 删除堆顶、根节点变小 | 从父节点到子节点 | 当前节点不小于两个子节点 |
| 向上堆化 | 尾部插入、节点值变大 | 从子节点到父节点 | 当前节点不大于父节点或到达根节点 |
完全二叉树的高度为 。一次堆化最多沿一条根到叶或叶到根的路径移动,因此时间复杂度为 ,额外空间复杂度为 。
完整可运行示例
下面的 Java 17 程序先对根节点执行向下堆化,再把新元素追加到数组末尾并执行向上堆化。两个方法都使用循环实现,避免递归调用带来的额外栈空间。
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));
}
}运行命令:
javac HeapifyDemo.java
java HeapifyDemo预期输出:
向下堆化: [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]。
本课练习
- 将示例改为最小堆,使父节点始终不大于子节点。分别调整比较条件,并用数组
[9, 4, 7, 1, 3]验证结果。 - 编写
isMaxHeap(int[] heap, int size),遍历所有非叶节点并返回堆是否合法。验收条件是合法最大堆返回true,任一父子关系违规时返回false。 - 增加
increaseKey(int[] heap, int index, int newValue)。要求拒绝比原值更小的新值,并通过向上堆化恢复最大堆。
本课总结
- 堆化只修复一条可能失序的路径,不需要重建整个堆
- 向下堆化选择较大的子节点,向上堆化持续比较父节点
- 两种操作最多移动一个树高,时间复杂度均为
下一课预告
下一课将学习“建堆与堆排序”,先用自底向上的方式在线性时间内建立最大堆,再通过反复交换堆顶完成原地升序排序。