堆如何删除任意位置的元素？为什么删除后可能上浮也可能下沉？

简化版

堆删除任意位置元素时，通常把最后一个元素搬到被删除位置，然后再修复堆序。

修复时可能需要上浮，也可能需要下沉：如果新元素比父节点更优，就上浮；如果它比某个子节点更差，就下沉。

普通堆删除任意元素的难点不在修复，而在「如何快速找到该元素的位置」。

详细版

删除下标 i 的元素可以分成几步：

用最后一个元素覆盖 heap[i]；
删除数组最后一位；
判断新元素应该上浮还是下沉；
更新堆。

removeAt(i):
  heap[i] = heap[last]
  remove last
  if heap[i] better than parent:
    siftUp(i)
  else:
    siftDown(i)

如果只有元素值而没有下标，普通堆要先 O(n) 查找。要做到高效删除，需要额外维护 value -> index 的映射，也就是类似索引堆。

完整版教学

1. 删除堆顶为什么简单

堆最擅长删除堆顶。

删除堆顶的流程是：

swap(heap[0], heap[last])
remove last
siftDown(0)

因为根节点被最后一个元素替换后，通常只可能比孩子更差，所以一路下沉即可。

任意位置删除比删除堆顶多一个判断：替换过来的元素可能需要向上，也可能需要向下。

2. 删除任意下标的标准流程

假设要删除下标 i。

第一步用最后一个元素填坑：

heap[i] = heap[n - 1]
n--

这样做的目的是保持数组堆的完全树结构。如果直接从中间删除，会破坏数组连续性和完全二叉树形态。

然后再根据堆序调整。

删除任意位置的关键动作是「最后元素填坑 + 局部修复」，不要把它理解成链表式的直接摘节点。

3. 为什么可能需要上浮

以小顶堆为例，如果替换过来的元素比父节点还小，它就应该向上走。

例如：

parent = 10
newValue = 3

此时 3 放在父节点下面违反了小顶堆性质，需要上浮。

while i > 0 and heap[i] < heap[parent(i)]:
  swap(i, parent(i))

4. 为什么可能需要下沉

如果替换过来的元素比父节点大，但比孩子也大，就需要向下走。

例如：

newValue = 20
child = 8

在小顶堆里，父节点应该不大于孩子。20 在 8 上面就违反堆序，所以要下沉。

下沉时要和更小的孩子交换。

5. 能不能先上浮再下沉

可以。

为了简化实现，可以执行：

j = siftUp(i)
siftDown(j)

或者先判断父子关系后只走一个方向。

写法	优点	缺点
判断后单方向	少做无用操作	分支逻辑稍多
先上浮再下沉	实现稳妥	可能多一点常数

无论哪种，复杂度仍然是 O(log n)。

6. 删除指定值的真正难点

如果函数参数是下标 i，删除修复是 O(log n)。

但如果参数是值 x，普通堆没有全局有序性，不知道 x 在哪。

这时需要：

find x: O(n)
removeAt(index): O(log n)

总复杂度会被查找拖成 O(n)。

7. 如何优化删除指定元素

常见方案有 3 种：

方案	思路	适合场景
线性查找	扫描堆数组	删除很少
索引堆	维护元素到下标映射	频繁删除或修改
懒删除	标记失效，堆顶再清理	标准库堆、不方便改内部结构

如果元素可能重复，映射不能只存一个下标，可能要存下标集合或唯一 id。

8. 常见误区与追问

误区：删除任意元素后一定只需要下沉。 替换元素可能比父节点更优，所以也可能需要上浮。
误区：普通堆删除指定值是 O(log n)。 如果不知道位置，查找指定值需要 O(n)。
误区：从数组中间直接删掉就行。 这样会破坏完全树对应的数组结构，通常要用最后元素填坑。
追问：重复元素怎么维护下标映射？ 可以给每个元素加唯一 id，或让 value 映射到多个下标。
追问：懒删除什么时候更合适？ 当使用语言标准库优先队列、无法直接访问内部堆数组时更方便。

简化版

详细版