41

STL で十分に機能すると思われるアプリケーション (C++) がありますpriority_queue。 ドキュメントには次のように記載されています。

Priority_queue はコンテナー アダプターです。つまり、基になるコンテナー タイプの上に実装されます。デフォルトでは、基になる型は vector ですが、別の型を明示的に選択することもできます。

と

プライオリティ キューは標準的な概念であり、さまざまな方法で実装できます。この実装はヒープを使用します。

私は以前、それが であり、それが(最初に を選択した 2 つの理由) であると想定していましたが、ドキュメントではこの仮定を確認も否定もしていません。top()O(1)push()O(logn)priority_queue

さらに深く掘り下げると、シーケンスの概念に関するドキュメントには次のように書かれています。

単一要素の挿入と消去の複雑さは、シーケンスに依存します。

は(デフォルトで) をヒープとしてpriority_queue使用します。vector

... 要素へのランダム アクセス、最後に要素を一定時間挿入および削除する機能、および最初または途中で要素を線形時間挿入および削除する機能をサポートします。

priority_queueデフォルトを使用して、top()isO(1)およびpush()isであると推測していますO(n)。

質問 1:これは正しいですか? （top()アクセスはO(1)ありpush()ますO(n)か？）

質問 2:の実装に(または) の代わりに(または)を使用した場合、O(logn)効率を上げることができますか? これを行うと、どのような結果が生じるでしょうか。結果として、他にどのような操作が影響を受けるでしょうか?push()setmultisetvectorpriority_queue

NB: ここで気になるのは時間効率であって、スペースではありません。

4

6 に答える 6

38

プライオリティ キュー アダプターは、標準ライブラリ ヒープ アルゴリズムを使用してキューを構築およびアクセスします。これらのアルゴリズムの複雑さについては、ドキュメントで調べてください。

top() 操作は明らかに O(1) ですが、おそらく呼び出した後にヒープを pop() したい ( Josuttisによると) O(2*log(N)) であり、 push() は O(log(N) です)) - 同じソース。

そして、C++ 標準、25.6.3.1、 push_heap から:

複雑さ: せいぜいログ (最後 - 最初) の比較。

および pop_heap:

複雑さ: 最大 2 * ログ (最後 - 最初) の比較。

于 2010-06-04T13:20:49.640 に答える
7

top()- O(1) -- 要素 @ front を返すだけです。

push()-

  • ベクターに挿入 - 0(1) 償却

  • push_into_heap - せいぜい log(n) 回の比較。O(ログ)

    したがって、push() の複雑さは -- log(n)

于 2010-06-04T13:28:42.350 に答える
5

いいえ、これは正しくありません。top() は O(1) で、push() は O(log n) です。ドキュメントの注 2 を読んで、このアダプターがベクターの反復を許可していないことを確認してください。Neil は pop() については正しいですが、それでもヒープを操作して O(log n) 時間で挿入と削除を行うことができます。

于 2010-06-04T13:24:43.547 に答える
2

基になるデータ構造がヒープの場合、top() は一定時間になり、push (EDIT: and pop) は対数になります (あなたが言っているように)。ベクトルは、次のようにこれらのものを格納するために使用されます。

ヒープ:
             1
        2 3
      8 12 11 9

VECTOR (保存に使用)

1 2 3 8 12 11 9

位置 i の子の要素は (2i) と (2i+1) であると考えることができます。

ベクトルを使用するのは、データを順次に格納するためです (離散よりもはるかに効率的でキャッシュに適しています)。

保存方法に関係なく、ポップが一定でプッシュが対数になるように、ヒープを常に実装する必要があります (特に STD ライブラリを作成した神々によって)。

于 2010-06-04T13:24:20.637 に答える
1

Q1: 私は標準を調べませんでしたが、私の知る限り、vector(またはdequeところで) を使用すると、複雑さはO(1)for top()、O(log n)forpush()およびpop(). std::priority_queue私は自分のヒープとO(1) push()andtop()とを比較したことがありますがO(log n) pop()、確かに ほど遅くはありませんでしたO(n)。

Q2: (シーケンスsetではない) の基になるコンテナーとして使用できませんが、 set を使用して、およびpriority_queueで優先キューを実装することは可能です。ただし、これはおそらく過剰な実装よりも優れているとは言えません。O(log n) push()pop()std::priority_queuestd::vector

于 2010-06-04T13:31:10.030 に答える