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