algorithm - 如何在堆数据结构中删除？

Question

我了解如何从最大堆中删除根节点，但是从中间删除节点的过程是重复删除和替换根直到删除所需节点的过程吗？

1. O(log n) 是这个过程的最优复杂度吗？

2. 这是否会影响大 O 复杂性，因为必须删除其他节点才能删除特定节点？

Answer 1

实际上，您可以毫不费力地从堆的中间移除一个项目。

想法是获取堆中的最后一个项目，并从当前位置(即保存您删除的项目的位置)开始，如果新项目大于旧项目的父项目，则将其向上筛选。如果它不大于父级，则将其向下筛选。

这是最大堆的过程。当然，对于最小堆，您会颠倒更大和更少的情况。

在堆中查找一个项目是一个 O(n) 操作，但如果您已经知道它在堆中的位置，则将其删除是 O(log n)。

几年前，我为 DevSource 发布了一个基于堆的优先级队列。完整来源位于 http://www.mischel.com/pubs/priqueue.zip

更新

有几个人问是否可以在移动堆中的最后一个节点以替换已删除的节点后向上移动。考虑这个堆:

        1
    6       2
  7   8   3

如果删除值为 7 的节点，则值 3 将替换它:

        1
    6       2
  3   8

您现在必须将其向上移动以形成有效堆:

        1
    3       2
  6   8

这里的关键是，如果您要替换的项与堆中的最后一项位于不同的子树中，则替换节点可能小于被替换节点的父节点。