从堆中删除元素：如何保证堆结构的正确性？

直接用堆尾元素替换待删除节点后只做向下heapify的问题在于，替换后的元素可能比其父节点更符合堆的优先级（比如最小堆里它比父节点小，最大堆里比父节点大），只下沉会忽略这种需要上浮的情况，进而破坏堆结构。正确的处理逻辑需要同时考虑向上调整和向下调整两个方向，步骤如下：

• 用堆的最后一个元素覆盖待删除节点的位置，随后将堆的大小减1（移除堆尾的冗余元素）
• 根据堆的类型（最小堆/最大堆）判断替换节点的调整方向：
  • 对于最小堆：如果当前节点值小于其父节点值，先向上交换调整，直到满足父节点小于等于子节点的性质；之后再检查是否需要向下调整（当前节点大于某个子节点时下沉）
  • 对于最大堆：如果当前节点值大于其父节点值，先向上交换调整，直到满足父节点大于等于子节点的性质；之后再检查是否需要向下调整（当前节点小于某个子节点时下沉）

代码示例（最小堆删除任意节点） #

def delete_min_heap_node(heap, target_idx):
    heap_size = len(heap)
    if target_idx >= heap_size:
        return heap
    
    # 替换待删除节点
    heap[target_idx] = heap[-1]
    heap.pop()
    heap_size -= 1
    current_idx = target_idx

    # 向上调整：如果当前节点比父节点小，上浮
    parent_idx = (current_idx - 1) // 2
    while current_idx > 0 and heap[current_idx] < heap[parent_idx]:
        heap[current_idx], heap[parent_idx] = heap[parent_idx], heap[current_idx]
        current_idx = parent_idx
        parent_idx = (current_idx - 1) // 2

    # 向下调整：如果当前节点比子节点大，下沉
    while True:
        left_child = 2 * current_idx + 1
        right_child = 2 * current_idx + 2
        smallest_idx = current_idx

        if left_child < heap_size and heap[left_child] < heap[smallest_idx]:
            smallest_idx = left_child
        if right_child < heap_size and heap[right_child] < heap[smallest_idx]:
            smallest_idx = right_child
        
        if smallest_idx != current_idx:
            heap[current_idx], heap[smallest_idx] = heap[smallest_idx], heap[current_idx]
            current_idx = smallest_idx
        else:
            break
    return heap

核心逻辑说明 #

替换后的节点可能处于一个“失衡”状态：它既可能比父节点更优（需要上浮到合适位置），也可能比子节点更差（需要下沉到合适位置）。只执行单一方向的heapify会漏掉其中一种情况，导致堆的部分子树不满足堆性质。通过先检查向上调整的必要性，再执行向下调整，就能确保整个堆的结构完整性。

内容的提问来源于stack exchange，提问作者Robo Jumble