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

问题描述

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

1. O（log n）是否为此过程的最佳复杂性？




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

解决方案>

实际上，您可以从堆中间移除一个项目，而不会有麻烦。

想法是将堆中的最后一个项目从当前位置（即保持您删除的项目的位置），如果新项目大于旧项目的父项，则将其筛选。如果不超过父级，则将其筛选。

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

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

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

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

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?

1. Is O(log n) the optimal complexity for this procedure?

2. 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.

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).

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.

Full source is at http://www.mischel.com/pubs/priqueue.zip

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