algorithm - Dijkstra 算法中堆相对于二叉树的优势

Question

Dijkstra 算法的一个标准实现使用堆来存储从起始节点 S 到所有未探索节点的距离。使用堆的论点是我们可以在 O(log n) 中有效地弹出距离它的最小距离。然而，为了保持算法的不变性，还需要更新堆中的一些距离。这涉及:

• 从堆中弹出非最小元素
• 计算更新的距离
• 将它们重新插入堆中

我知道从堆中弹出非最小元素可以在 O(log n) 中完成，前提是知道该元素在堆中的位置。但是，我不明白在 Dijkstra 算法的情况下如何知道这个位置。听起来二叉搜索树更合适。

更一般地说，我的理解是堆唯一能比平衡二叉搜索树做得更好的是访问(而不删除)最小元素。我的理解正确吗？

Answer 1

However, I fail to understand how one can know this location in the case of the Dijkstra algorithm.

您需要一个额外的数组来跟踪元素在堆中的位置，或者需要一个额外的数据成员在堆的元素中。这必须在每次堆操作后更新。

the only thing that a heap can do better than a balanced binary search tree is to access (without removing) the min element

即使 BST 也可以修改为除了根指针之外还保留指向最小元素的指针，从而使 O(1) 可以访问最小元素(有效地分摊 O(lg n) 的工作超过其他操作)。

堆在最坏情况下的复杂性方面的唯一优势是“heapify”算法，它通过在线性时间内就地重新排列数组的元素，将数组变成堆。对于 Dijkstra 来说，这无关紧要，因为它要执行 n 个 O(lg n) 的堆操作，无论如何都要花费。

那么，堆的真正原因是常量。正确实现的堆只是一个连续的元素数组，而 BST 是一个指针结构。即使在数组内实现 BST(如果从一开始就知道元素的数量就可以做到，就像 Dijkstra 的那样)，指针会占用更多的内存，并且导航它们比使用的整数运算花费更多的时间导航堆。