26

を使用して最小ヒープを作成するために、なぜ を使用priority_queueするstd::greater必要があるのでしょうか?

std::priority_queue<T, std::vector<T>, std::greater<T> > min_heap;

私にとって、最小値は常にヒープの一番上にあるため、採用クラスはstd::less

更新: 一方、priority_queue(最大ヒープ) のデフォルトの動作は最大値を一番上に保持することであるstd::greaterため、最小ヒープの作成ではなく、最大ヒープの作成に使用する必要があるように見えます

4

3 に答える 3

9

論理的な議論は次のとおりです

  1. std::priority_queueコンテナ アダプタです。基本的なメモリの考慮事項により、などのシーケンス コンテナーの変更 (pop_back()および を使用) には、背面が優先されます。 push_back()std::vector
  2. priority_queueプリミティブはstd::make_heap(コンストラクター)、std::pop_heap+ container::pop_back( priority_queue::pop) およびcontainer::push_back+ std::push_heap( priority_queue::push)に基づいています。
  3. pop_heap基礎となるストレージの前面を取り、それを背面に置き、後でヒープ不変を復元します。の場合は逆ですpush_heap。
  4. a で実行sort_heapするとmax_heap(最初は最大値が前面にある) 、前面が背面に繰り返しポップlessされ、 (デフォルトの比較演算子)に従って範囲が並べ替えられます。
  5. したがって、 a の推奨される実装は、最前部にmax_heapwrt という最大要素を持ち、(基になる) を介してアクセスすることです。lesspriority_queue::topcontainer::front
  6. コンパレータをpriority_queue使用してを表すことが直感的かどうかについては、まだ議論の余地があります。さまざまなヒープ関数の呼び出しのどこでも、コンパレーターの引数を逆にすることで (ただし、C++98 バインダーではかなり冗長であるという @TC のコメントを参照してください)として定義することもできます。（私にとって）直観に反する結果の 1 つは、最優先の要素が与えられなかったことです。std::lessmax_heapmin_heaptop()
于 2015-09-23T20:41:34.117 に答える
7

C++ ヒープ関数make_heap、push_heap、およびはmax heappop_heapで動作します。つまり、既定のコンパレータを使用すると、最上位の要素が最大になります。したがって、最小ヒープを作成するには、代わりにを使用する必要があります。greater<T>less<T>

最小ヒープの代わりに最大ヒープが使用されているのは、less操作で実装する方が簡単だからだと思います。C++ では、lessすべての STL アルゴリズムの一種の「デフォルト」コンパレータであるという特別な特権があります。1 つの比較演算 ( 以外==) のみを実装する場合は、 にする必要があります<。priority_queue<T, C<T>, less<T>>これは、最大キューと最小キューを意味する不幸な癖につながりpriority_queue<T, C<T>, greater<T>>ます。

また、次のような特定のアルゴリズムにnth_elementは最大ヒープが必要です。

于 2015-09-23T19:40:23.447 に答える
-1

http://en.cppreference.com/w/cpp/container/priority_queueを参照してください。Apriority_queueは、最大値が上に来るように設計されています。std::lessこれは、デフォルトのコンパレータを使用した場合に発生します。したがって、逆の動作が必要な場合は、逆コンパレータを使用する必要がありますstd::greater。

于 2015-09-23T19:43:16.517 に答える