什么时候最好在
Dijkstra中实现优先级队列作为最小堆，什么时候使用普通数组更好？
一个有运行时间O(V^2 + E)，另一个O((V+E)logV)。当E< V ，则 O(V^2+E) = O(V^2)，比O((V+E)logV)=O(2VlogV)=O(VlogV)更糟糕
当V< E时，O(V^2 + E)= O(E^2)和O((V+E)logV) = O(ElogV)，所以堆实现似乎又更好了。
它们也具有相同的空间复杂性，即O(n)。
我假设在某些情况下，Dijkstra 中最小优先级队列的简单数组实现更好，但实际上想不出情况。
对于Dijkstra，正如@JimMischel所说，我想不出任何例子，我认为它不存在。但是，对于UCS（统一成本搜索），它侧重于查找到单个完成节点的单个最短路径，而不是到每个节点的最短路径，我可以想到一个例子。这将涉及国家之间过渡是统一的问题。
例如，假设我们正在解决 15 个难题（所有转换的成本为 1）。此外，在这类问题中，解决方案成本的范围是众所周知的，因此您可以探索一系列状态，其中对于每个成本，您存储具有这种成本的简单路径向量。在这种情况下，每个操作都有O(1)，使用数组比使用二进制最小堆更有效。