ダイクストラ アルゴリズムの標準的な実装の 1 つは、ヒープを使用して、開始ノード S から未調査のすべてのノードまでの距離を格納します。ヒープを使用する理由は、ヒープから最小距離を効率的にポップできることO(log n)です。ただし、アルゴリズムの不変条件を維持するには、ヒープ内の距離の一部を更新する必要もあります。これには以下が含まれます。
O(log n)ヒープ内のその要素の場所を知っていれば、ヒープから非最小要素をポップできることを理解しています。ただし、ダイクストラ アルゴリズムの場合、この場所を知る方法がわかりません。二分探索木がより適切であるように思えます。
より一般的には、ヒープがバランスのとれた二分探索木よりも優れているのは、min 要素に (削除せずに) アクセスすることだけだと理解しています。私の理解は正しいですか？
ただし、ダイクストラ アルゴリズムの場合、この場所を知る方法がわかりません。
要素が存在するヒープ内の場所を追跡する追加の配列、またはヒープの要素内の追加のデータ メンバーが必要です。これは、各ヒープ操作の後に更新する必要があります。
ヒープがバランスの取れた二分探索木よりも優れている唯一のことは、min 要素に (削除せずに) アクセスすることです。
BST でさえ、ルート ポインターに加えて min 要素へのポインターを保持するように修正して、min への O(1) アクセスを許可することができます (O(lg n ) の作業を他の操作より効果的に償却します)。
最悪の場合の複雑さに関するヒープの唯一の利点は、「ヒープ化」アルゴリズムです。これは、線形時間でその要素をインプレースで再シャッフルすることにより、配列をヒープに変換します。Dijkstra の場合、これは問題ではありません。とにかく、O(lg n ) のn 個のヒープ操作を行うためです。
したがって、ヒープの本当の理由は定数です。適切に実装されたヒープは要素の連続した配列にすぎませんが、BST はポインター構造です。BST が配列内に実装されている場合でも (Dijkstra のように、要素の数が最初からわかっている場合は実行できます)、ポインターはより多くのメモリを消費し、それらをナビゲートするには、使用される整数演算よりも多くの時間がかかります。ヒープをナビゲートします。