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

Question

我理解如何从最大堆中删除根节点,但是是否从中间删除节点以重复删除和替换根,直到删除所需节点为止？

1. O(log n)是此过程的最佳复杂性吗？

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

Answer 1

实际上,您可以毫无困难地从堆中间删除项目.

我们的想法是获取堆中的最后一项,并从当前位置(即保留您删除的项目的位置)开始,如果新项目大于旧项目的父项,则将其筛选.如果它不大于父母,那么将其筛选下来.

这是最大堆的过程.当然,对于最小堆,您可以反转更大和更少的情况.

在堆中查找项是O(n)操作,但如果您已经知道它在堆中的位置,则删除它是O(log n).

几年前我为DevSource发布了一个基于堆的优先级队列.请参阅C#中的优先级队列实现.它有一种RemoveAt方法完全符合我的描述.

完整资料来源是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

这里的关键是,如果要替换的项目与堆中的最后一项不同,则替换节点可能小于替换节点的父节点.

Answer 2

从堆中删除任意元素的问题是您无法找到它.

在堆中,查找任意元素O(n),因此删除元素[如果按值给出]也是O(n)如此.

如果从数据结构中删除任意元素很重要,那么堆可能不是最佳选择,您应该考虑完整的排序数据结构,例如平衡BST或跳过列表.

如果你的元素是通过引用给出的,那么可以O(logn)通过简单地用最后一个叶子"替换" 来删除它[记住一个堆被实现为一个完整的二叉树,所以有最后一个叶子,你知道确切的位置它是],删除这些元素,并重新堆积相关的子堆.