83

std::priority_queueとstd::set(および) は両方とも、std::multiset要素を格納し、順序付けられた方法でそれらにアクセスできるようにするデータ コンテナーであり、挿入の複雑さは同じでO(log n)あるため、一方を他方よりも使用する利点は何ですか (または、どのような状況で 1 つが必要になるか)それとも他の？）？

基礎となる構造が異なることは知っていますが、パフォーマンスとさまざまな用途への適合性を比較するときほど、実装の違いには興味がありません。

注:セット内の重複なしについては知っています。std::multisetとまったく同じ動作をしますstd::setが、保存されたデータが等しい要素として比較できる場所で使用できるため、私も言及したのはそのためです。したがって、単一/複数のキーの問題についてコメントしないでください。

4

4 に答える 4

72

プライオリティ キューでは、ソートされた順序で1 つの要素にのみアクセスできます。つまり、最も優先度の高いアイテムを取得でき、それを削除すると、次に優先度の高いアイテムを取得できます。プライオリティ キューでは要素の重複も許可されるため、セットというよりはマルチセットに似ています。[編集: @Tadeusz Kopec が指摘したように、ヒープの構築は、ヒープ内のアイテムの数にも線形であり、セットの構築は O(N log N) であり、既に順序付けられたシーケンスから構築されている場合を除きます (その場合それも線形です）。

セットを使用すると、ソートされた順序で完全にアクセスできるため、たとえば、セットの途中で 2 つの要素を見つけて、一方から他方へと順番にトラバースできます。

于 2012-04-13T13:38:10.683 に答える
60

std::priority_queue次のことができます。

  1. 要素を挿入するO(log n)
  2. 最小の要素を取得するO(1)
  3. 最小要素を消去O(log n)

whilestd::setにはより多くの可能性があります:

  1. 任意の要素を挿入O(log n)し、定数が in より大きいstd::priority_queue
  2. 任意の要素を検索O(log n)
  3. >= あなたが探しているものよりも要素を見つけてくださいO(log n)( lower_bound)
  4. 任意の要素を消去O(log n)
  5. その要素によって任意の要素を消去しますiterator O(1)
  6. ソートされた順序で前/次の要素に移動O(1)
  7. 最小の要素を取得するO(1)
  8. 最大の要素を取得するO(1)
于 2012-04-13T13:44:19.757 に答える
36

set/multiset は通常、バイナリ ツリーに支えられています。 http://en.wikipedia.org/wiki/Binary_tree

通常、priority_queue はヒープに支えられています。 http://en.wikipedia.org/wiki/Heap_(データ構造)

問題は、いつヒープの代わりにバイナリ ツリーを使用する必要があるかということです。

どちらの構造もツリーに配置されていますが、祖先間の関係に関する規則は異なります。

親を P、左の子を L、右の子を R と呼びます。

二分木では L < P < R.

ヒープ内 P < L および P < R

したがって、二分木は「横向き」にソートされ、ヒープは「上向き」にソートされます。

したがって、これを三角形として見ると、二分木では L、P、R が完全にソートされますが、ヒープでは L と R の関係は不明です (P との関係のみ)。

これには次の効果があります。

  • ソートされていない配列があり、それを二分木に変換したい場合、時間がかかりO(nlogn)ます。それをヒープに変えたい場合はO(n)、時間がかかるだけです（極端な要素を見つけるために比較するだけなので）

  • 極端な要素 (いくつかの比較関数による最低または最高) のみが必要な場合、ヒープはより効率的です。ヒープは、極端な要素を決定するために必要な比較のみを (遅延して) 行います。

  • 二分木は、コレクション全体を並べ替えるために必要な比較を実行し、コレクション全体を常にソートした状態に保ちます。

  • ヒープには最低要素の定数時間ルックアップ (ピーク) があり、バイナリ ツリーには最低要素の対数時間ルックアップがあります。

于 2012-04-13T13:36:15.713 に答える