[c++] 最小優先度キューをC ++でのキー更新で使用する最も簡単な方法



Answers

私の応答は元の質問に答えることはできませんが、DijkstraアルゴリズムをC ++ / Java(自分のように)で実装しようとしたときにこの問題に遭遇した人、

前に述べたように、C ++(またはJavaのPriorityQueue )のpriority_queueは、 decrease-key操作をdecrease-keyません。 Dijkstraを実装するときにこれらのクラスを使用するための素晴らしいテクニックは、「遅延削除」を使用しています。 Dijkstraアルゴリズムのメインループは、処理すべき次のノードを優先キューから抽出し、その隣接ノードをすべて分析し、最終的に優先キュー内のノードの最小パスのコストを変更する。 これは、そのノードの値を更新するために通常はreduce decrease-keyが必要なポイントです。

トリックはそれをまったく変更しません 。 その代わりに、そのノードの「新しいコピー」(新しいコストがより高い)が優先キューに追加されます。 より低コストであるため、ノードの新しいコピーは、キュー内の元のコピーの前に抽出されるので、より早く処理されます。

この「怠惰な削除」の問題は、ノードの第2のコピーが、より高いコストを伴って、最終的に優先度キューから抽出されることである。 しかし、それは、より良いコストで、2番目に追加されたコピーが処理された後に常に発生します。 したがってプライオリティキューから次のノードを抽出するときに、ダイクストラのメインループが最初に行う必要があるのは、ノードが以前に訪問されたかどうかをチェックすることです(最短パスはすでにわかっています)。 私たちが "怠惰な削除"を行う正確な瞬間にあり、その要素は単に無視されなければなりません。

優先度キューは削除していない「不足要素」を格納しているため、このソリューションではメモリと時間の両方でコストがかかります。 実際のコストは非常に小さく、このソリューションをプログラミングすることは、欠けているdecrease-key操作をシミュレートしようとする他のどの方法よりも簡単です。

Question

時にはプログラミングコンテストなどで、私たちはDijkstraアルゴリズムなどを実装するためにreduceキーを使った最小優先順位キューの簡単な実装が必要です。set <pair <key_value、ID>>および配列(IDのマッピング - > key_value )それを達成するために一緒に。

  • 集合に要素を追加するには、O(log(N))時間が必要です。 N要素から優先度キューを構築するには、それらを1つずつセットに追加するだけです。 これは合計でO(N log(N))時間かかる。

  • min key_valueを持つ要素は、単にセットの最初の要素です。 最小の要素を探索するにはO(1)時間がかかります。 それを削除するにはO(log(N))時間がかかります。

  • いくつかのID = kがセット内にあるかどうかをテストするために、まず配列内のkey_value = v_kを検索し、そのセット内の要素(v_k、k)を検索します。 これにはO(log(N))時間がかかります。

  • いくつかのID = kのkey_valueをv_kからv_k 'に変更するには、まず配列内のkey_value = v_kを検索し、次にセット内の要素(v_k、k)を検索します。 次に、その要素を集合から削除し、要素(v_k '、k)を集合に挿入します。 その後、配列も更新します。 これにはO(log(N))時間がかかります。

上記のアプローチは機能しますが、ほとんどの教科書は、バイナリヒープを構築する時間がちょうどO(N)であるため、通常、プライオリティキューを実装するためにバイナリヒープを使用することを推奨しています。 私はバイナリヒープを使用するC ++のSTLにビルトインプライオリティキューデータ構造があると聞いています。 しかし、私はどのようにそのデータ構造のkey_valueを更新するのか分からない。

C ++でのキー更新でmin優先度キューを使用する最も簡単で効率的な方法は何ですか?




Links