C / C++ / 系统课时
插入元素后怎样向上调整
插入元素后怎样向上调整
最大堆插入新元素时,最方便的位置是数组末尾,但新值可能比父节点更大,从而破坏最大堆规则。本节用数组下标和完整 C 代码实现“追加后向上调整”,并验证元素如何沿父节点方向逐层交换到正确位置。
学习目标
- 理解为什么堆插入先把新元素追加到数组末尾
- 掌握父节点下标计算和向上调整的停止条件
- 能用 C 语言实现最大堆的插入操作并验证结果
从数组末尾开始修复
使用从 0 开始的数组存储完全二叉树时,下标为 i 的非根节点,其父节点下标为 (i - 1) / 2。插入时先把新元素放到当前堆的末尾,这样不会破坏完全二叉树的形状,只需要处理大小关系。
假设已有最大堆对应数组为 90, 70, 80, 40, 60, 50, 65,现在插入 85。追加后新元素位于下标 7,它的父节点下标为 3,对应值 40。因为 85 > 40,两者交换;随后 85 到达下标 3,再与下标 1 的 70 比较并交换。最后它遇到父节点 90,此时满足最大堆规则,调整结束。

向上调整的核心规则
向上调整只需要重复执行三个动作:找到父节点、比较当前元素与父节点、必要时交换。只要当前节点不是根节点,并且它比父节点大,就继续向上移动。
停止条件有两个:当前元素已经到达根节点,或者当前元素不大于父节点。后一种情况意味着当前位置以上原本就是合法最大堆,因此无需继续比较祖先节点。
这种方法也常称为上滤或 sift up。每交换一次,元素最多向上移动一层,而完全二叉树高度约为 log2(n),所以一次插入的时间复杂度为 O(log n)。
用 C 语言实现插入
下面的程序从一个合法最大堆开始插入 85。heap_insert 先扩展逻辑长度,再通过父节点下标不断向上交换。
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heap_insert(int heap[], int *size, int value) {
int i = *size;
heap[i] = value;
(*size)++;
// 新元素只可能破坏它与祖先之间的最大堆关系。
while (i > 0) {
int parent = (i - 1) / 2;
if (heap[parent] >= heap[i]) {
break;
}
swap(&heap[parent], &heap[i]);
i = parent;
}
}
int main(void) {
int heap[16] = {90, 70, 80, 40, 60, 50, 65};
int size = 7;
heap_insert(heap, &size, 85);
for (int i = 0; i < size; i++) {
printf("%d%s", heap[i], i == size - 1 ? "\n" : " ");
}
return 0;
}预期输出
90 85 80 70 60 50 65 40输出仍满足最大堆规则:任意父节点都不小于自己的孩子,同时数组元素连续存放,没有产生空洞。
容易写错的边界
计算父节点之前必须先保证 i > 0。根节点下标为 0,它没有父节点;如果直接对根节点计算 (i - 1) / 2,在使用无符号下标时还可能发生下溢。
另一个常见错误是交换后没有执行 i = parent。交换只是把元素移动了一层,新位置仍可能比新的父节点大,因此必须更新当前下标并继续检查。实际实现中还应在写入数组末尾前确认容量足够,避免插入导致越界。
向上调整的关键不是重新扫描整个堆,而是利用“插入前原堆已经合法”这一条件,只沿新元素到根节点的唯一路径修复,因此能把一次插入控制在 O(log n)。