跟踪一个堆内的节点

Question

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

我的目标是在每个堆中为每个节点位置保留某种记录，并使用堆行为更新它。底线 - 我想弄清楚如何有一个删除（P）函数在LG（N）复杂的作品。 p是一个可以容纳任何数据的指针数据对象。

谢谢， 内德。

Answer 1

如果您的堆是以项目数组的形式实现的（例如引用），那么您可以在O（n）时间内轻松地在堆中找到任意项。一旦你知道该项目在堆中的位置，你可以在O（log n）时间内删除它。所以找到并移除是O（n + log n）。

如果您将堆与字典或散列图配对，您可以实现O（log n）删除，如我在this answer中所述。

删除O（log n）时间中的任意项目将被解释为here。

字典方法的诀窍是字典包含一个键（项目键）和一个值，该值是堆中节点的位置。无论何时移动堆中的节点，都会更新字典中的值。插入和删除在这种情况下稍慢，因为它们需要补足log（n）字典更新。但那些更新是O（1），所以它不是巨大昂贵。或者，如果你的堆实现为二叉树（带有指针，而不是数组中的隐式结构），那么你可以在字典中存储一个指向节点的指针，而不必在插入时更新它或从堆中移除。

也就是说，实际性能的成对数据结构中的添加和删除min（或删除最大堆数）将低于使用作为数组实现的标准堆的性能，除非您做了大量的任意删除操作。如果你每隔一段时间只删除一个任意的项目，特别是如果你的堆很小，那么你最好使用O（n）删除性能。实现起来比较简单，当n很小时，O（n）和O（log n）之间几乎没有什么区别。