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 开始寻找较大孩子并向下交换。

c
#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;
}

预期输出

text
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。只沿被替换元素所在路径向下修复,就能避免重新遍历整个堆。

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

目录与阅读设置

阅读设置

17

记录一个想法

删除堆顶后怎样向下调整

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

登录哪都通