最小ヒープと通常配列の通常の配列の実装

Question

Dijkstraの優先順位キューをminヒープとして実装するのが最善の場合はどのような場合ですか？

実行時間はO(V^2 + E)で、もう1つはO((V+E)logV)です。ときE< Vので、ヒープの実装が良いと再び思えるときV< E、O(V^2 + E)= O(E^2)とO((V+E)logV) = O(ElogV)、その後、 O(V^2+E) = O(V^2)、それはO((V+E)logV)=O(2VlogV)=O(VlogV)

よりも悪いです。

これらは同じスペースの複雑さも持っています。つまり、O(n)です。

Dijkstraの最小優先度キューの単純な配列実装が優れているが、実際にはケースを考えることができない場合があると仮定します。

Answer 1

@JimMischelとしてのダイクストラについては、私はどの例も考えることができず、それは存在しないと思います。しかし、すべてのノードへの最短経路ではなく、単一の仕上げノードへの単一の最短経路を見つけることに重点を置くUCS（Uniform cost search）では、例を考えることができます。これは、状態間の遷移が一様であるという問題を伴います。

たとえば、15個のパズルを解決しているとしましょう（すべてのトランジションのコストは1です）。さらに、この種の問題では、ソリューションコストの範囲はよくわかっています。したがって、コストごとに、コストのかかるパスの単純なベクトルを格納するために、探索すべき状態の配列を持つことができます。この場合、すべての演算にはO(1)があり、バイナリminヒープよりも配列を使用するほうが効率的です。