跟踪一个节点的堆内 [英] Tracking a node inside an heap

问题描述

我有这个问题 - 我保持一种数据结构，包含两个不同的堆，一个最小堆和最大堆不包含相同的数据。

I have this problem - i'm keeping a data structure that contains two different heaps , a minimum heap and a maximum heap that does not contain the same data.

我的目标是保持了一个记录的无论是在堆的每个节点的位置，并将它与堆动作更新。 底线 - 我试图找出我怎么能有一个delete（P）的功能，在LG电子（n）的复杂工作。 p是可容纳任何数据的指针数据对象。

My goal is to keep some kind of record for each node location in either of the heaps and have it updated with the heaps action. Bottom line - i'm trying to figure out how can i have a delete(p) function that works in lg(n) complexity. p being a pointer data object that can hold any data.

谢谢， 斯内德。

推荐答案

如果您的堆实现为项目（参考文献，说的）数组，那么你可以很容易地找到任意一个项目堆在O（n）时间。一旦你知道该项目是在堆中，你可以在O（log n）的时间将其删除。所以，找到并删除为O（n + log n）的。

If your heap is implemented as an array of items (references, say), then you can easily locate an arbitrary item in the heap in O(n) time. And once you know where the item is in the heap, you can delete it in O(log n) time. So find and remove is O(n + log n).

可以达到O（log n）的去除，如果你配对堆有一本字典或哈希地图，我描述本回答。

You can achieve O(log n) for removal if you pair the heap with a dictionary or hash map, as I describe in this answer.

删除O型任意项（log n）的时间是解释这里。

Deleting an arbitrary item in O(log n) time is explained here.

诀窍字典的方法是，在字典中包含一个键（ITEM键）和值是堆中节点的位置。每当你在堆中移动节点时，更新在字典中的价值。插入和移除是在这种情况下稍微慢一些，因为它们需要构成记录（n）的词典更新。但是，这些更新是O（1），所以它不是的非常的昂贵。

The trick to the dictionary approach is that the dictionary contains a key (the item key) and a value that is the node's position in the heap. Whenever you move a node in the heap, you update that value in the dictionary. Insertion and removal are slightly slower in this case, because they require making up to log(n) dictionary updates. But those updates are O(1), so it's not hugely expensive.

或者，如果你的堆实现为二叉树（使用指针，而不是隐式结构数组），那么你可以存储一个指针在字典中的节点，而不必更新它，当你插入或从堆中删除。

Or, if your heap is implemented as a binary tree (with pointers, rather than the implicit structure in an array), then you can store a pointer to the node in the dictionary and not have to update it when you insert or remove from the heap.

话虽这么说，在添加的实际的性能和删除分钟（或删除最大为最大堆）在配对的数据结构会比与的方式实现作为阵列的标准堆越低，除非你做了很多随心所欲的删除。如果你只是删除任意项目每过一段时间，特别是如果你的堆是相当小的，你可能会更好的为O（n）删除的性能。这是容易实现，当n为小有O（n）和O（​​log n）的。之间几乎没有真正的区别

That being said, the actual performance of add and delete min (or delete max for the max heap) in the paired data structure will be lower than with a standard heap that's implemented as an array, unless you're doing a lot of arbitrary deletes. If you're only deleting an arbitrary item every once in a while, especially if your heap is rather small, you're probably better off with the O(n) delete performance. It's simpler to implement and when n is small there's little real difference between O(n) and O(log n).

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