C / C++ / 系统课时
删除堆顶后怎样向下调整
删除堆顶后怎样向下调整
最大堆的堆顶就是最大值,但直接删除数组下标 0 会破坏完全二叉树的连续结构。标准做法是先用末尾元素覆盖堆顶,再缩短堆长度,然后让这个元素不断与较大的孩子交换,直到整棵堆重新满足最大堆规则。
学习目标
- 理解删除堆顶时为什么要用末尾元素补到根节点
- 掌握向下调整时选择较大孩子的原因和停止条件
- 能用 C 语言实现删除最大值并验证调整后的堆
删除后先保持树的形状
假设最大堆数组为 90, 85, 80, 70, 60, 50, 65, 40。删除最大值 90 后,如果把其余元素整体向前移动,不仅成本高,也没有利用堆的结构特征。
更高效的做法是把最后一个元素 40 放到下标 0,再把堆的逻辑长度从 8 减到 7。这样完全二叉树的形状仍然正确,只是新的根节点可能比孩子小,需要从根开始向下修复。

为什么必须选择较大的孩子
对于下标 i,左孩子下标为 2 * i + 1,右孩子下标为 2 * i + 2。向下调整时,如果两个孩子都存在,应该先找出其中较大的一个,再判断当前元素是否需要与它交换。
以上面的 40 为例,根节点两个孩子分别是 85 和 80。如果错误地与较小的 80 交换,新的根虽然变成 80,但它仍小于另一个孩子 85,最大堆规则依旧被破坏。因此必须与两个孩子中的较大者交换。
交换后继续在新位置重复同样操作。只要当前节点已经不小于较大孩子,或者它已经没有孩子,就可以停止。这个过程通常称为下滤或 sift down。
用 C 语言删除最大值
下面实现 heap_remove_max。函数先保存根节点,再用最后一个有效元素覆盖根节点,随后从下标 0 开始寻找较大孩子并向下交换。
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int heap_remove_max(int heap[], int *size, int *removed) {
if (*size == 0) {
return 0;
}
*removed = heap[0];
(*size)--;
if (*size == 0) {
return 1;
}
heap[0] = heap[*size];
int i = 0;
// 每次选择更大的孩子,才能一次修复当前层的最大堆关系。
while (1) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < *size && heap[left] > heap[largest]) {
largest = left;
}
if (right < *size && heap[right] > heap[largest]) {
largest = right;
}
if (largest == i) {
break;
}
swap(&heap[i], &heap[largest]);
i = largest;
}
return 1;
}
int main(void) {
int heap[] = {90, 85, 80, 70, 60, 50, 65, 40};
int size = 8;
int removed;
if (heap_remove_max(heap, &size, &removed)) {
printf("removed: %d\n", removed);
printf("heap: ");
for (int i = 0; i < size; i++) {
printf("%d%s", heap[i], i == size - 1 ? "\n" : " ");
}
}
return 0;
}预期输出
removed: 90
heap: 85 70 80 40 60 50 65删除后的数组仍连续保存完全二叉树,并且 85、70、80 等父节点都不小于各自孩子,因此已经恢复为合法最大堆。
边界与复杂度
空堆没有可删除的堆顶,因此示例先检查 *size == 0 并返回失败。只有一个元素时,减小长度后堆已经为空,也不需要再执行向下调整。
向下调整每交换一次最多下降一层,最大堆的高度约为 log2(n),所以删除堆顶的时间复杂度为 O(log n)。取得堆顶值本身是 O(1),真正的成本来自末尾元素补到根节点后的结构修复。
实现时最值得检查的是左右孩子的边界条件。最后一层可能只有左孩子,因此访问 heap[right] 之前必须确认 right < *size。只沿被替换元素所在路径向下修复,就能避免重新遍历整个堆。