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


Answers

私は、 std::priority_queueクラスがstd::priority_queue decrease-keyスタイル操作の効率的な実装を可能にするとは思わない。

私は自分自身のバイナリヒープベースのデータ構造をロールバックして、これをサポートしています。基本的には、あなたが持っているstd::setベースの優先度キューについて説明したものと非常によく似た行になります。

  • pair<value, ID>要素とID -> heap_indexをマップする配列を格納するvalueでソートされたバイナリヒープを維持します。 ヒープルーチンheapify_up, heapify_downなどの中では、マッピング配列が要素の現在のヒープ位置と同期していることを保証する必要があります。 これにより、余分なO(1)オーバーヘッドが追加されます。
  • 配列のヒープへの変換は、 ここで説明する標準アルゴリズムに従ってO(N)行うことができます
  • ルート要素でのピックはO(1)です。
  • IDが現在ヒープ内にあるかどうかを確認するには、マッピング配列にO(1)ルックアップが必要です。 これにより、任意のID対応する要素でO(1)こともできID
  • Decrease-keyは、マッピング配列内のO(1)ルックアップと、 heapify_up, heapify_down介したヒープへのO(log(N))更新がheapify_up, heapify_downです。
  • 新しい項目をヒープにプッシュすると、ヒープから終了する項目をポップするときにO(log(N))なります。

したがって、ランタイムは、 std::set基づくデータ構造と比較して、いくつかの操作で漸進的に改善されています。 もう一つの重要な改良点は、バイナリ・ヒープを配列に実装できることです。バイナリ・ツリーはノード・ベースのコンテナです。 バイナリヒープの余分なデータ局所性は通常、ランタイムの改善につながります。

この実装に関するいくつかの問題は次のとおりです。

  • それは整数項目IDだけを許可します。
  • これは、ゼロから始まるアイテムIDのタイトな分布を前提としています(そうしないと、マッピング配列の空間複雑さが爆発的に上がります)。

マッピング配列ではなくマッピングのハッシュテーブルを維持していても、実行時のオーバーヘッドが少し増えると、これらの問題を潜在的に克服できます。 私の使用のために、整数IDは常に十分であった。

お役に立てれば。

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優先度キューを使用する最も簡単で効率的な方法は何ですか?