堆是如何删除堆顶元素的？什么是「下沉」？

简化版

删除堆顶（取最值）分三步：先取出堆顶（数组第 0 个）作为返回值；把最后一个元素移到堆顶（填补空缺、保持完全二叉树）；然后让它下沉（sift down）——不断和较大的孩子（大顶堆）或较小的孩子（小顶堆）比较，若违反堆序就交换下沉，直到就位或成为叶子。O(log n)。

详细版

以大顶堆为例：

int poll(int[] heap) {          // 取出并删除最大值
    int top = heap[0];          // 1. 堆顶就是最大值
    heap[0] = heap[--size];     // 2. 最后一个元素移到堆顶
    siftDown(heap, 0);          // 3. 下沉
    return top;
}
void siftDown(int[] heap, int i) {
    while (true) {
        int l = 2*i+1, r = 2*i+2, largest = i;
        if (l < size && heap[l] > heap[largest]) largest = l;
        if (r < size && heap[r] > heap[largest]) largest = r;  // 找最大的孩子
        if (largest == i) break;              // 已满足堆序
        swap(heap, i, largest);               // 和较大孩子交换，下沉
        i = largest;
    }
}

移最后一个到堆顶：末尾元素删掉不影响结构，把它顶到根来填补。
下沉：这个元素通常较小，要和「较大的那个孩子」交换往下走（小顶堆则和较小孩子）。

完整版教学

一、为什么用「最后一个元素填堆顶」

删掉堆顶后，根的位置空了。如果直接把某个孩子提上来，会连锁地在下面留下更多空洞，破坏完全二叉树结构。最巧妙的做法是：把数组最后一个元素移到堆顶。因为删掉「最后一个」不会破坏完全二叉树（末尾正是可以安全移除的位置），移到堆顶后结构依然完整。代价是这个元素通常很小（它本来在底层），放到堆顶违反了堆序，所以要下沉修正。

二、下沉：把「太小的」往下送，且要和较大孩子换

下沉的关键细节是：必须和「较大的那个孩子」交换（大顶堆）。为什么？因为交换上来的孩子要当新的父节点，它必须 ≥ 另一个孩子才满足堆序。如果和较小的孩子换，换上来的还是比另一个孩子小，堆序仍被破坏。所以每一步：

找出左右孩子中较大的那个。
如果当前节点比这个较大孩子还小（违反父 ≥ 子），就和它交换、下沉一层。
重复，直到比两个孩子都大（就位）或没有孩子（成为叶子）。

小顶堆对称：和较小的孩子比较、交换。

三、走一个例子

大顶堆 [10,7,9,3,5,8] 删除堆顶 10：
1) 取出 10
2) 末尾 8 移到堆顶: [8,7,9,3,5]（size 从 6 变 5）
3) 下沉 8:
   孩子 l=1(7), r=2(9)，较大是 9 > 8 → 交换 → [9,7,8,3,5]，i=2
   i=2 的孩子 l=5 越界(size=5)，无孩子 → 停止
结果堆顶变成次大值 9 ✓

四、复杂度

时间 O(log n)：下沉最多走一条到叶子的路径，长度 = 树高 = log n。
空间 O(1)：原地交换。

peek（只看堆顶不删）是 O(1)——直接返回 heap[0]。

五、易错点

必须和较大/较小的孩子换：大顶堆和较大孩子换、小顶堆和较小孩子换，换错会破坏堆序。
孩子越界检查：l < size、r < size 才是有效孩子（可能只有左孩子或没有孩子）。
先取堆顶再覆盖：先保存 heap[0] 作返回值，再用末尾元素覆盖它。
size 要先减：末尾元素被移走后，堆的有效范围缩小 1。

六、常见误区与追问

考点	正确口径
删除对象	只能直接删除堆顶最优元素
补位	用最后一个元素放到堆顶保持形状
下沉	和更优孩子交换，直到堆序恢复

ans = heap[0]
heap[0] = heap[last]
remove last
siftDown(0)
return ans

删除堆顶也是先保形状，再修堆序；下沉时必须选择两个孩子中更优的那个。

误区：删除堆顶后可以直接把左孩子提上来。 这样可能破坏完全二叉树形状，标准做法是用最后一个元素补根。
误区：下沉时随便和一个孩子交换。 大顶堆必须和较大孩子交换，小顶堆必须和较小孩子交换，否则另一侧可能仍破坏堆序。
误区：poll 后数组末尾元素可以不删除。 不删除会留下重复元素，也会让堆大小错误。
追问：为什么下沉只走一条路径？ 每次把当前元素放到更合适的一侧，未交换的子树仍然保持堆序。
追问：复杂度是多少？ 最多从根下沉到叶子，时间 O(log n)，额外空间 O(1)。
追问：堆能高效删除任意元素吗？ 普通堆不能直接定位任意元素；需要索引表辅助，或接受 O(n) 查找。

七、加强记忆

删堆顶三步：取出 heap[0]（返回最值）→ 末尾元素移到堆顶（保持完全二叉树）→ 下沉（siftDown）：和较大孩子（大顶堆）/较小孩子（小顶堆）比较，违反堆序就交换往下，直到就位或成叶子。O(log n)，peek 是 O(1)。关键：下沉必须和「较大/较小的那个孩子」换，且要判孩子越界。

简化版

详细版