从堆删除第i个节点 [英] Delete ith node from a Heap

问题描述

我知道，从堆删除一个节点是 O（log n）的的occures的根源。而且我也知道，删除在堆树问题之一堆任意节点，是 O（N）。

I know that deleting a node from a heap is O(log n) that occures at the root. And I also know that deleting an arbitrary node in a heap in one of the heap tree problems and is O(n).

有没有什么算法，减少了删除的第I 的节点从maxheap到 0的运行时间（log n）的其中的 I 的范围是从1到N？

Is there any algorithm that reduces the running time of deleting the Ith node from a maxheap to O(log n) where I is ranging from 1 to N?

推荐答案

这堆删除一个任意节点的昂贵的部分不处于删除，但在发现删除的节点。其实删除节点是O（log n）的。但首先你要做的底层数据存储的顺序扫描，以查找节点。这就是O（n）的部分。

The expensive part of deleting an arbitrary node from a heap isn't in the deleting, but in finding the node to delete. Actually deleting the node is O(log n). But first you have to do a sequential scan of the underlying data store in order to find the node. That's the O(n) part.

要加快这唯一的办法是保持第二数据结构就像一本字典或哈希映射或类似的，可以迅速告诉你，该项目是在后备存储。然后你有一个O（1）查找在词典中，一个O从字典（1）清除，和O（log n）的去除堆。

The only way to speed this up is to keep a second data structure like a dictionary or hash map or similar that can quickly tell you where the item is in the backing store. Then you have an O(1) lookup in the dictionary, an O(1) removal from the dictionary, and an O(log n) removal from the heap.

这篇关于从堆删除第i个节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！