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

Question

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

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

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

Answer 1

索引 (id, node) 可以单独维护在具有 O(1) 查找复杂度(平均)的哈希表中。总体复杂度仍然是 O(log n)。