数据结构：从堆中删除元素 (Deleting from a Heap)
目录
定义问题
一个直接但不靠谱的想法
从“结构属性”出发寻找解决方案
推导“下沉”操作来修复堆序
完善代码
定义问题
首先，我们必须明确“删除”的含义。在一个堆（特别是我们用作“优先队列”时），最有意义的删除操作是 “删除最大值”（对于大顶堆）。
因为堆这个结构的核心优势就是能以 O(1) 的时间复杂度访问到最大值。所以，我们通常说的“堆的删除”，指的就是 extractMax (取出最大值) 这个操作。
数据结构：堆（Heap）-CSDN博客
📌 目标：从堆中移除根节点（最大值），并让剩下的元素重新构成一个合法的堆，同时返回被移除的那个最大值。
一个直接但不靠谱的想法
最大值就在数组的 data[0] 位置。最简单的想法是：直接把它删掉。
[100, 90, 80, 70] -> [?, 90, 80, 70]
但这会留下一个“窟窿”在堆顶，整个结构被破坏了，它甚至不再是一棵连通的树。这个方法行不通。
从“结构属性”出发寻找解决方案
和插入操作一样，我们优先考虑如何维护 “结构属性”，也就是保证操作后它仍然是一棵完全二叉树。
如果我们删除堆顶，树的形状就被破坏了。但如果我们删除的是最后一个元素呢？
[100, 90, 80, 70] -> [100, 90, 80] 剩下的部分 [100, 90, 80] 仍然完美地对应一棵完全二叉树。
💡 这个观察给了我们一个绝妙的思路来“修复”删除堆顶后留下的窟窿：
-
我们先把要删除的根节点的值（最大值）保存起来，因为最后要返回它。
-
我们把堆的最后一个元素（在数组的
data[size-1]位置）拿出来。 -
用这个“最后的元素”去填补根节点的窟窿。
-
然后，把堆的
size减一，逻辑上就相当于删除了最后一个元素。
这样操作之后，我们得到的树在形状上一定是正确的（仍然是完全二叉树），但堆序属性❌几乎肯定被破坏了。
举个例子，假设原来的堆是：
逻辑结构：
100/ \90 80/70数组表示: [100, 90, 80, 70] (size = 4)
我们要删除 100。
-
保存
100这个值。 -
拿出最后一个元素
70，放到根节点的位置。 -
size减为 3。
现在的数组变成了 [70, 90, 80]。 对应的逻辑结构是：
70 <-- 堆序被破坏！/ \90 80我们看到，根节点 70 比它的两个孩子 90 和 80 都小，这严重违反了堆序属性。
推导“下沉”操作来修复堆序
现在的问题是，一个（可能很小的）元素被放到了堆顶，它需要找到自己“合适”的位置。这个过程和插入时的“上浮”正好相反，我们称之为 “下沉” (Sift Down)。
下沉的逻辑推导：
-
当前的节点（一开始是根节点）的值，和它的两个孩子比较。
-
如果它的值比两个孩子都大（或等于），那么堆序属性在这一点得到了满足，下沉结束。
-
如果它的值比至少一个孩子小，为了满足堆序，它必须和值更大的那个孩子交换位置
-
交换位置后，这个节点来到了一个新的、更低的位置。它可能仍然比它的新孩子要小，所以我们必须重复第1步，继续向下比较和交换。
❓为什么是和更大的孩子交换
思考一下：如果和较小的孩子交换，那么那个更大的孩子仍然会比新的父节点（就是被换下来的那个较小孩子）要大，堆序属性依然是错的。所以，必须让最大的元素“上位”。
这个过程一直持续，直到这个节点“下沉”到了一个合适的位置（它比它的两个孩子都大），或者它自己变成了叶子节点（没有孩子了），就停止。
让我们用上面的例子来走一遍“下沉”流程：
70 <-- 堆序被破坏！/ \90 80-
初始状态:
[70, 90, 80]，当前节点是70(下标0)。 -
第一次比较:
70的孩子是90(下标1) 和80(下标2)。70小于它们。 -
选择交换对象: 两个孩子中，
90是更大的那个。 -
交换:
70和90交换位置。数组变为[90, 70, 80]。 -
更新位置:
70现在来到了下标1的位置。 -
继续下沉: 检查下标为
1的节点70。它有孩子吗？根据size=3，它的左孩子下标2*1+1=3已经超出了范围，所以它现在是叶子节点，没有孩子了。 -
下沉结束。最终数组为
[90, 70, 80]，它代表的树重新满足了堆序。
完善代码
首先，我们需要一个 siftDown 的辅助函数。这个函数非常重要，是堆的核心操作之一。
// (之前已经有 swap 函数)// siftDown (下沉) 操作
// h: 堆的指针
// index: 从哪个位置开始进行下沉操作
void siftDown(Heap* h, int index) {int currentIndex = index;// 循环条件：只要当前节点有左孩子（有左必有右或无右，保证不是叶子节点）while (leftChild(currentIndex) < h->size) {int largerChildIndex = leftChild(currentIndex);int rightChildIndex = rightChild(currentIndex);// 检查是否存在右孩子，并且右孩子比左孩子更大if (rightChildIndex < h->size && h->data[rightChildIndex] > h->data[largerChildIndex]) {largerChildIndex = rightChildIndex;}// 如果当前节点已经比它最大的孩子要大，说明位置正确，停止下沉if (h->data[currentIndex] >= h->data[largerChildIndex]) {break;}// 否则，和更大的孩子交换swap(&h->data[currentIndex], &h->data[largerChildIndex]);// 更新当前索引，继续向下检查currentIndex = largerChildIndex;}
}// extractMax (删除并返回最大值) 函数
int extractMax(Heap* h) {// 检查堆是否为空if (h->size <= 0) {std::cout << "错误：堆为空。\n";return -1; // 返回一个错误码}// 1. 保存根节点的值（最大值）int maxValue = h->data[0];// 2. 将最后一个元素移动到根节点h->data[0] = h->data[h->size - 1];// 3. 堆的大小减一h->size--;// 4. 从根节点开始执行“下沉”操作，以恢复堆序siftDown(h, 0);// 5. 返回最大值return maxValue;
}复杂度分析： “下沉”操作的路径也是从根到底，所以它的时间复杂度也是由树高决定的，即 O(logN)。