algorithm - 跟踪堆内的节点

Question

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

我的目标是为任一堆中的每个节点位置保留某种记录，并使用堆操作对其进行更新。底线 - 我试图弄清楚我怎样才能拥有一个在 lg(n) 复杂性中工作的 delete(p) 函数。p 是可以保存任何数据的指针数据对象。

谢谢，内德。

Answer 1

如果您的堆被实现为一个项目数组（例如引用），那么您可以在 O(n) 时间内轻松地在堆中找到任意项目。一旦您知道该项目在堆中的位置，您就可以在 O(log n) 时间内将其删除。所以查找和删除是 O(n + log n)。

如果将堆与字典或哈希映射配对，则可以实现 O(log n) 的删除，正如我在此答案中所描述的那样。

这里解释了在 O(log n) 时间内删除任意项目。

字典方法的技巧是字典包含一个键（项目键）和一个值，该值是节点在堆中的位置。每当您在堆中移动一个节点时，都会在字典中更新该值。在这种情况下，插入和删除会稍微慢一些，因为它们需要进行 log(n) 字典更新。但是这些更新是 O(1)，所以它并不是非常昂贵。

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

话虽如此，成对数据结构中添加和删除最小值（或最大堆的删除最大值）的实际性能将低于作为数组实现的标准堆，除非您正在执行大量任意删除. 如果您只是偶尔删除一个任意项目，特别是如果您的堆相当小，那么 O(n) 删除性能可能会更好。实现起来更简单，当 n 很小时，O(n) 和 O(log n) 之间几乎没有真正的区别。