当前位置：首页 > ai >正文

数据结构：在堆中插入元素（Inserting In a Heap）

ai 2025/8/28 10:01:41

我们的目标和约束

如何满足“结构属性”？

怎样修改被破坏的“堆序属性”？

完善代码

总结与分析

现在我们已经深刻理解了堆的静态结构——它是一个用数组表示的、满足特定属性的完全二叉树。

接下来，我们就来探讨如何向这个结构中添加一个新元素，也就是 insert 操作。

我们的目标和约束

当我们向堆中插入一个新元素时，我们的最终目标是：操作完成后，这个数据结构仍然必须是一个合法的堆。

这意味着，插入操作结束后，必须同时满足堆的两条核心属性：

结构属性：它必须仍然是一棵完全二叉树。
堆序属性：所有父节点的值必须仍然大于或等于其子节点的值（以大顶堆为例）。

数据结构：堆（Heap）-CSDN博客

我们必须在这两条约束下，找到插入新元素的位置和方法。

如何满足“结构属性”？

我们先来解决相对容易的“结构属性”。为了在插入一个新节点后，整棵树依然是“完全”的，新节点应该放在哪里？

根据完全二叉树的定义（从上到下、从左到右依次填满），新节点有且仅有一个唯一的位置可以放：就是当前这棵树最后一个节点的下一个位置。

在我们的数组表示法中，这个操作极其简单：

如果当前堆中有 size 个元素（存储在数组的 0 到 size-1 位置），那么这个“下一个位置”就是数组的下标 size。

所以，插入操作的第一步，就是把新元素放到数组当前最后一个元素的后面，然后把 size 加一。

让我们把这个初步想法写成代码：

// 接着上次的代码
#include <iostream>// (这里是之前定义的 Heap 结构体和 parent, leftChild, rightChild 函数)
// ...// 向堆中插入一个元素
void insert(Heap* h, int value) {// 预先检查：堆是不是已经满了？if (h->size == h->capacity) {std::cout << "错误：堆已满，无法插入新元素。\n";return;}// --- 第一步：满足结构属性 ---// 将新元素放置在数组的末尾h->data[h->size] = value;// 堆中的元素数量加一h->size++;// ... 接下来该做什么？
}

到这里，我们成功地满足了“结构属性”。但这显然还没完。

怎样修改被破坏的“堆序属性”？

我们虽然保证了树的“形状”是正确的，但“堆序属性”很可能已经被我们破坏了。

举个例子。假设我们原来的堆是这样的：

逻辑结构:

      100/   \70    80

数组表示: [100, 70, 80] (size = 3)

现在，我们要插入一个新值：90。

按照第二步的操作，我们把它放在数组末尾： [100, 70, 80, 90] (size = 4)

这对应的新逻辑结构是：

      100/   \70    80/90      <-- 新插入的节点

现在我们来检查“堆序属性”。新节点 90 的父节点是谁？

90 的下标是 3。
它的父节点下标是 parent(3) = (3 - 1) / 2 = 1。
下标 1 的值是 70。

⚠️ 我们发现 90 > 70，也就是 子节点 > 父节点。这严重违反了“堆序属性”！

如何修复？

问题出在子节点比父节点大。最直接、最符合逻辑的修复方法，就是把它们两个交换位置，让大的上去，小的下来。

我们来交换 90 (下标3) 和 70 (下标1)： [100, 90, 80, 70]

交换后的逻辑结构：

      100/   \90    80/70

我们再检查一下。90 现在换到了新的位置（下标1），它有了新的父节点 100（下标0）。 90 < 100，满足了堆序属性。并且，被换下来的 70 的父节点是 90，70 < 90，也满足。

看起来问题解决了。

我们再考虑一个更极端的情况，假设我们要插入的值是 200 呢？

初始状态: [100, 70, 80]
插入 200: [100, 70, 80, 200]，结构正确，但 200 > 70，堆序被破坏。
第一次交换: 200 和它的父节点 70 交换。

[100, 200, 80, 70] 现在 200 的下标是 1。我们必须继续检查它和它的新父节点的关系。

200 的新父节点是 parent(1) = (1 - 1) / 2 = 0，对应的值是 100。我们发现 200 > 100，堆序仍然是错误的，只不过问题向上移动了一层。

从上面的过程我们可以总结出一个规律：

当一个新节点插入后，它可能会比它的父节点大，于是我们交换它们。

交换后，这个节点来到了新的位置，我们必须重复这个过程：继续拿它和新的父节点比较，如果还是比父节点大，就继续交换。

这个过程就像一个气泡在水中不断上浮一样，我们称这个过程为 “上浮” (Sift Up 或 Bubble Up)。

这个“上浮”过程什么时候停止呢❓❓❓

当这个节点“上浮”到了根节点的位置（它的下标已经是0），没有父节点了，自然就停了。
或者，在“上浮”的某个过程中，我们发现它已经不比它的父节点大了，那么堆序属性在这一点以及以上部分都得到了满足，也可以停了。

完善代码

现在，我们可以把“上浮”这个逻辑添加到我们的 insert 函数中了。

// 为了代码清晰，我们先写一个交换函数
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 完整的 insert 函数
void insert(Heap* h, int value) {// 1. 检查容量if (h->size == h->capacity) {std::cout << "错误：堆已满，无法插入新元素。\n";return;}// 2. 将新元素放置在数组的末尾，并增加 sizeh->data[h->size] = value;int currentIndex = h->size; // 记录新元素的当前位置h->size++;// 3. 执行“上浮”操作，恢复堆序属性// 循环条件：只要当前节点不是根节点，并且它的值比父节点大while (currentIndex > 0 && h->data[currentIndex] > h->data[parent(currentIndex)]) {// 交换当前节点和它的父节点swap(&h->data[currentIndex], &h->data[parent(currentIndex)]);// 将索引更新为父节点的索引，为下一次循环做准备currentIndex = parent(currentIndex);}
}