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

• Z时代
• 2024-01-10
• 分类：问答

我知道如何从最大堆中删除根节点，但是是否要从中间删除节点的过程重复删除并替换根，直到删除所需的节点？

1. O（log n）是此过程的最佳复杂度吗？

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

回答：

实际上，您可以轻松地从堆中间删除项目。

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

这就是最大堆的过程。当然，对于最小堆，您可以颠倒大小写的情况。

__在堆中 查找 项目是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

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

以上是 如何删除堆中的数据结构？ 的全部内容， 来源链接： utcz.com/qa/399960.html