如何在一个堆数据结构中删除 [英] How to delete in a heap data structure

问题描述

我知道如何删除最大堆根节点，但对于删除一个节点，从中间反复拆卸和更换根，直到所需的节点被删除的程序？

I understand how to delete the root node from a max heap but is the procedure for deleting a node from the middle to remove and replace the root repeatedly until the desired node is deleted?

2）为O（log n）的这个过程的正确的复杂性 3）这是否会影响大O的复杂性，因为其他节点必须以删除特定的节点被删除？

2) Is O(log n) the correct complexity for this procedure 3) Does this affect the big O complexity since other nodes must be deleted in order to delete a specific node?

推荐答案

其实，你可以从一堆不麻烦的中间删除项目。我们的想法是把堆的最后一个项目，并从当前位置开始（即持有已删除项目的位置），筛选起来，如果新产品比老项目的父。如果不是比母体更大，然后筛选下来。

Actually, you can remove an item from the middle of a heap without trouble. The idea is to take the last item in the heap and, starting from the current position (i.e. the position that held the item you deleted), sift it up if the new item is greater than the parent of the old item. If it's not greater than the parent, then sift it down.

这是一个最大堆的过程。当然，对于最小堆，你会扭转越来越少的情况下。

That's the procedure for a max heap. For a min heap, of course, you'd reverse the greater and less cases.

查找的在堆项目是一个O（n）的操作，但如果你已经知道它是在堆中，删除它是O（log n）的。

Finding an item in a heap is an O(n) operation, but if you already know where it is in the heap, removing it is O(log n).

我发表了DevSource基于堆的优先级队列在几年前。请参见在C＃优先级队列实现。它有一个 RemoveAt 方法，它不正是我所描述。

I published a heap-based priority queue for DevSource a few years back. See A Priority Queue Implementation in C#. It has a RemoveAt method that does exactly what I described.

完整的源是 http://www.mischel.com/pubs/priqueue.zip

这篇关于如何在一个堆数据结构中删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！