目录
现在我们已经深刻理解了堆的静态结构——它是一个用数组表示的、满足特定属性的完全二叉树。
接下来，我们就来探讨如何向这个结构中添加一个新元素，也就是 insert 操作。
我们的目标和约束
当我们向堆中插入一个新元素时，我们的最终目标是：操作完成后，这个数据结构仍然必须是一个合法的堆。
这意味着，插入操作结束后，必须同时满足堆的两条核心属性：
结构属性：它必须仍然是一棵完全二叉树。
堆序属性：所有父节点的值必须仍然大于或等于其子节点的值（以大顶堆为例）。
我们必须在这两条约束下，找到插入新元素的位置和方法。
如何满足“结构属性”？
我们先来解决相对容易的“结构属性”。为了在插入一个新节点后，整棵树依然是“完全”的，新节点应该放在哪里？
根据完全二叉树的定义（从上到下、从左到右依次填满），新节点有且仅有一个唯一的位置可以放：就是当前这棵树最后一个节点的下一个位置。
在我们的数组表示法中，这个操作极其简单：
如果当前堆中有
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. 将新元素放置在数组的末尾，并增加 size
h->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);
}
}总结与分析
我们通过一步步的推导，最终完成了 insert 函数。回顾一下整个过程：
根本目的：插入后，结构必须还是一个合法的堆。
拆分问题：分别考虑“结构属性”和“堆序属性”。
解决结构属性：将新元素放在数组末尾，这是唯一解。
发现新问题：这样做可能会破坏“堆序属性”。
解决堆序属性：通过“上浮”（不断与父节点比较并交换）操作，自下而上地修复堆序。
时间复杂度分析： 这个“上浮”的过程，最坏情况下是从树的最底层一直“浮”到树的顶端（根节点）。它走过的路径长度就是这棵树的高度。
我们知道，一个包含 N 个节点的完全二叉树，其高度为 O(logN)。 因此，堆的插入操作的时间复杂度是 O(logN)。
这个结果非常理想！它远远优于有序数组的 O(N)，也解决了我们最初提出的那个问题：找到一个能够同时“比较快”地查找最大值（对于堆是 O(1)）和“比较快”地插入新元素（O(logN)）的数据结构。