从堆中间删除节点

Question

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

一种解决方案可以是我们可以在每个节点中具有位置的地址,其中我们维护堆中节点的索引.该数组将按节点ID排序.这需要维护额外的阵列.有没有其他好方法来实现同样的目标.

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

Answer 1

索引（id，节点）可以单独维护在哈希表中，其查找复杂度（平均）为 O(1)。总体复杂度仍然是 O(log n)。