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 先扩展逻辑长度,再通过父节点下标不断向上交换。

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

预期输出

text
90 85 80 70 60 50 65 40

输出仍满足最大堆规则:任意父节点都不小于自己的孩子,同时数组元素连续存放,没有产生空洞。

容易写错的边界

计算父节点之前必须先保证 i > 0。根节点下标为 0,它没有父节点;如果直接对根节点计算 (i - 1) / 2,在使用无符号下标时还可能发生下溢。

另一个常见错误是交换后没有执行 i = parent。交换只是把元素移动了一层,新位置仍可能比新的父节点大,因此必须更新当前下标并继续检查。实际实现中还应在写入数组末尾前确认容量足够,避免插入导致越界。

向上调整的关键不是重新扫描整个堆,而是利用“插入前原堆已经合法”这一条件,只沿新元素到根节点的唯一路径修复,因此能把一次插入控制在 O(log n)。

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

目录与阅读设置

阅读设置

17

记录一个想法

插入元素后怎样向上调整

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

登录哪都通