我尝试在不使用优先级队列(Heap)的情况下在循环加权图上使用Djikstra算法,并且它有效.
然后我搜索谷歌"为什么我们需要一个优先级队列来实现这个？" 作为搜索的结果,我浏览了维基百科,在那里我了解到原始实现不使用优先级队列并在O(| V | 2)中运行,即V平方时间.
现在,如果我们只删除优先级队列并使用正常队列,则运行时间是线性的,即O(V + E).
请有人建议那么为什么我们需要优先队列？
我尝试使用外部排序来回答这个问题,但是访问者回答说复杂性是高nn(log(n)),即n square*logn.有没有更好的选择.
为了简化问题:让我们假设我们有1000个元素要排序,只为100个元素分配空间.什么是比外部排序花费更少时间的最佳算法.