Dijkstra 算法的一种标准实现使用堆来存储从起始节点 S 到所有未探索节点的距离。使用堆的理由是我们可以有效地弹出与它的最小距离，in O(log n)。但是，为了保持算法的不变性，还需要更新堆中的一些距离。这涉及：
O(log n)我知道如果知道堆中该元素的位置，则可以从堆中弹出非最小元素。但是，我不明白在 Dijkstra 算法的情况下如何知道这个位置。听起来二叉搜索树会更合适。
更一般地说，我的理解是，堆比平衡二叉搜索树做得更好的唯一一件事就是访问（不删除）最小元素。我的理解正确吗？
但是，我不明白在 Dijkstra 算法的情况下如何知道这个位置。
您需要一个额外的数组来跟踪元素在堆中的位置，或者在堆的元素中添加一个额外的数据成员。这必须在每次堆操作后更新。
堆比平衡二叉搜索树做得更好的唯一一件事是访问（不删除）最小元素
甚至可以修改 BST 以在根指针之外保留指向 min 元素的指针，从而使 O(1) 访问 min （有效地将 O(lg n ) 工作摊销给其他操作）。
堆在最坏情况复杂性方面的唯一优势是“堆化”算法，该算法通过在线性时间内就地重新排列其元素将数组变成堆。对于 Dijkstra 来说，这无关紧要，因为无论如何它都会执行O(lg n )的n 个堆操作。
那么，堆的真正原因是常量。正确实现的堆只是一个连续的元素数组，而 BST 是一个指针结构。即使在数组中实现 BST（如果从一开始就知道元素的数量，就可以做到这一点，如 Dijkstra 的），指针占用更多内存，并且导航它们比使用的整数操作花费更多时间导航堆。