43

ヒープを作成するために使用したいベクトルがあります。C++ の make_heap 関数を使用するべきか、ベクターを優先キューに入れるべきかわかりません。性能的にはどちらが優れていますか？いつどちらを使用する必要がありますか?

4

6 に答える 6

46

性能面での違いはありません。std::priority_queueコンテナーとまったく同じヒープ関連の関数呼び出しをクラスにラップする単なるアダプター クラスです。の仕様はstd::priority_queue公然と述べています。

公開されたヒープ関連の関数から を構築して直接呼び出すと、外部アクセスの可能性にheapさらされたままになり、ヒープ/キューの整合性が損なわれる可能性があります。そのアクセスを「標準的な」最小値に制限するバリアとして機能します:std::vectorstd::priority_queuepush()pop()top()

また、キュー インターフェイスを「標準的な」一連の操作に適合させることで、同じ外部仕様に準拠する優先度キューの他のクラスベースの実装と統一し、交換可能にします。

于 2012-06-29T17:47:04.433 に答える
8

priority_queue は (少なくとも通常は) ヒープとして実装されます。そのため、本当の問題は、priority_queue が必要なものを提供するかどうかです。make_heap を使用すると、すべての要素にアクセスできます。priority_queue を使用すると、要素へのアクセスが非常に制限された少数の操作しかありません (基本的には、アイテムを挿入し、キューの先頭にあるアイテムを削除するだけです)。

于 2012-06-29T17:47:20.780 に答える
6

C++11 標準

C++11 N3337 標準ドラフトは、「23.6.4.1 priority_queue コンストラクター」std::make_heapのコンストラクターで使用されることを指定します。std::priority_queue

明示的な優先順位キュー

2 効果: comp を x で初期化し、c を y で初期化します (必要に応じて、コピー構築または移動構築)。make_heap(c.begin(), c.end(), comp) を呼び出します。

そして他の方法は言う：

void push(const value_type& x);

効果: c.push_back(x); push_heap(c.begin(), c.end(), comp)

ただし、新しいn4724の時点では、非コンストラクターメソッドの表現は「あたかも」になるため、*_heapメソッドの実際の呼び出しは保証されておらず、機能的な動作のみが保証されていると思います。

これはすべて、 https://stackoverflow.com/a/11266558/895245std::priority_queueがラッパーであることについて言及したことを裏付けていますstd::make_heap。

g++6.4 stdlibc++ ソースにステップ デバッグして、priority_queue転送先を確認します。make_heap

Ubuntu の 16.04 デフォルトg++-6パッケージまたはソースからの GCC 6.4 ビルドでは、追加のセットアップなしで C++ ライブラリにステップインできます。

これを使用すると、 が基になる を持つファミリstd::priority_queueの単なるラッパーであることを簡単に確認できます。これは、パフォーマンスが同じであることを意味します。std::make_heapstd::vector

a.cpp:

#include <cassert>
#include <queue>

int main() {
    std::priority_queue<int> q;
    q.emplace(2);
    q.emplace(1);
    q.emplace(3);
    assert(q.top() == 3);
    q.pop();
    assert(q.top() == 2);
    q.pop();
    assert(q.top() == 1);
    q.pop();
}

コンパイルおよびデバッグ:

g++ -g -std=c++11 -O0 -o a.out ./a.cpp
gdb -ex 'start' -q --args a.out

ここで、std::priority_queue<int> q最初にコンストラクターにステップインすると、コンストラクターに入ります。vectorそのためstd::priority_queue、 にstd::vector.

ここでfinish、GDB で実行してキュー コンストラクターを見つけ、再びステップ インします。これにより、実際のキュー コンストラクターが表示されます/usr/include/c++/6/bits/stl_queue.h。

443       explicit
444       priority_queue(const _Compare& __x = _Compare(),
445              _Sequence&& __s = _Sequence())
446       : c(std::move(__s)), comp(__x)
447       { std::make_heap(c.begin(), c.end(), comp); }

これは明らかに、オブジェクトstd::make_heapの上に転送するだけです。c

でソース ファイルを開き、次vimの定義を見つけますc。

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {

      [...]

      _Sequence  c;

cしたがって、それは であると結論付けvectorます。

他のメソッドに足を踏み入れるか、ソースをさらに調べると、他のすべてのpriority_queueメソッドもstd::make_heap関数のファミリに転送されていることが簡単にわかります。

平均挿入時間はヒープの方が短いため、ヒープとバランスの取れた BST の選択は理にかなっています。参照:ヒープとバイナリ検索ツリー (BST)

于 2018-08-21T09:23:30.347 に答える
2

priority_queueコンテナではありません。vectorこれは、や などの特定の基礎となるコンテナーを使用するコンテナー アダプターでdequeあり、データを操作するための特定のメソッド セットを提供します。*_heapさらに、その実装はアルゴリズムに依存しています。

たとえば、新しい値を にプッシュするときはいつでも、vector呼び出しpush_heapてヒープと見なされる範囲を拡張する必要があります。を使用しない場合priority_queue、たとえば、 の半分をvectorヒープ ( std::make_heap(v.begin(), v.begin() + (v.size() / 2))) と見なすことができますが、残りの半分はそのままになります。

priority_queueそれを呼び出すとどうなるかpush: 新しい要素を基になるコンテナーの後ろにプッシュしpush_heap、ヒープ プロパティを優先して保持するように呼び出します (最初の要素が最大であることが重要です)。

パフォーマンスの問題よりも、ソリューションの設計と特定の要件を検討したほうがよいと思います。

于 2012-06-29T19:01:39.330 に答える
0

make_heap を使用すると、たとえばヒープを出力するなど、カプセル化を犠牲にして柔軟性を得ることができます。

make_heap の興味深い使用法は、マージの片側で make_heap を使用するインプレース マージ ソートで、n/2(log(n/2)) の最悪のケースのインプレース マージを実現します。

この例は、入力ベクトルの使用と、作成されたヒープの出力を示しています。

#include <queue>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void print(string prefix,vector<int>& v)
{
  cout << prefix;
  for(int i : v)
     cout << i << " ";
  cout << endl;
}

int main()
{
  vector<int> v={1,2,9,0,3,8,4,7,1,2,9,0,3,8,4,7};
  typedef priority_queue< int,vector<int>,greater<int> > MinQ;
  MinQ minQ(v.begin(),v.end()); //minQ
  print("After priority_queue constructor: ",v);

  make_heap(v.begin(),v.end(),greater<int>());
  print("After make_heap: ", v);
  return 0;
}

出力：

After priority_queue constructor: 1 2 9 0 3 8 4 7 1 2 9 0 3 8 4 7
After make_heap: 0 1 0 1 2 3 4 7 2 3 9 8 9 8 4 7
于 2018-07-28T05:01:48.703 に答える