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

Question

Dijkstra算法的一个标准实现使用堆来存储从起始节点S到所有未探测节点的距离。使用堆的理由是，我们可以有效地弹出与堆之间的最小距离，在＜code＞O（log n）

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

我知道从堆中弹出非最小元素可以在O（log n）中完成，如果一个人知道该元素在堆中的位置。但是，我不明白在Dijkstra算法的情况下如何知道这个位置。听起来二叉查找树更合适。

更一般地说，我的理解是，堆唯一能比平衡的二叉搜索树做得更好的事情就是访问（不删除）min元素。我的理解是否正确？

Answer 1

然而，我无法理解在Dijkstra算法的情况下如何知道这个位置。

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

堆唯一比平衡二叉查找树做得更好的是访问（不删除）min元素

甚至可以修改BST，除了根指针之外，还保留一个指向min元素的指针，使O(1)访问min(有效地将O(lg n)工作分摊到其他操作上)。

就最坏情况复杂性而言，堆的唯一优势是“heapify”算法，该算法通过在线性时间内重新排列其元素，将数组转换为堆。对于Dijkstra来说，这并不重要，因为它将进行O（lgn）的n个堆操作，每个操作的成本都是。

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