algorithm - 从堆的中间删除一个节点

Question

从堆中间删除一个节点可以在 O(lg n) 中完成，前提是我们可以在恒定时间内找到堆中的元素。假设堆的节点包含 id 作为其字段。现在，如果我们提供 id，我们如何在 O(lg n) 时间内删除节点？

一种解决方案是我们可以在每个节点中拥有一个位置的地址，我们在其中维护堆中节点的索引。该数组将按节点 ID 排序。不过，这需要维护额外的数组。有没有其他好的方法可以达到同样的效果。

PS：我在实现 Djikstra 的最短路径算法时遇到了这个问题。

Answer 1

索引 (id, node) 可以在具有 O(1) 查找复杂度（平均）的哈希表中单独维护。然后整体复杂度保持为 O(log n)。

Answer 2

每个数据结构的设计都考虑了某些操作。来自关于堆操作的维基百科

堆通常执行的操作是：
 create-heap：创建一个空堆
find-max 或 find-min：找到最大堆的最大项或最小堆的最小项，分别为
delete-max 或 delete -min：删除最大或最小堆的根节点，分别
增加键或减少键：分别更新最大或最小堆中
的键插入：将新键添加到堆
合并加入两个堆以形成一个有效的新堆，其中包含两者的所有元素。

这意味着，堆不是您正在寻找的操作的最佳数据结构。我建议您寻找更适合的数据结构（取决于您的要求）..

Answer 3

我遇到了类似的问题，这就是我想出的：

解决方案 1：如果您删除某些随机项的调用将有一个指向项的指针，您可以将您的个人数据项存储在堆外；堆是指向这些项目的指针；并让每个项目包含其当前的堆数组索引。

示例：堆包含指向键为 [2 10 5 11 12 6] 的项的指针。持有值 10 的项目有一个名为 ArrayIndex = 1 的字段（从 0 开始计数）。因此，如果我有一个指向第 10 项的指针并想要删除它，我只需查看它的 ArrayIndex 并在堆中使用它进行正常删除。O(1) 找到堆位置，然后通常 O(log n) 通过递归 heapify 删除它。

解决方案 2：如果您只有要删除的项目的关键字段，而不是其地址，请尝试此操作。切换到红黑树，将有效负载数据放入实际的树节点中。对于插入和删除，这也是 O( log n )。它还可以在 O( log n ) 中找到具有给定键的项目，这使得 delete-by-key 继续为 log n。

在这些之间，解决方案 1 将需要在每次交换时不断更新 ArrayIndex 字段的开销。这也导致了一种奇怪的一次性数据结构，下一个代码维护者需要研究和理解。我认为解决方案 2 的速度差不多，并且具有易于理解的算法的优势。