`priority_queue 'でminヒープを作成するために` std :: greater`を使用する理由

Question

priority_queueを使用してミニヒープを作成する理由は？std::greaterを使用するのはなぜですか？私に

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

最小値は常にヒープの最上部に位置しているため、採用のクラスはstd::less

を更新する必要があります：priority_queueのデフォルトの動作であるため、一方 （最大ヒープ）C++のヒープ関数は、make_heap分ヒープを作成するため

Answer 1

1. std::priority_queueは、容器アダプタで次のように論理的な引数です。基本的なメモリの考慮事項は、std::vectorのようなシーケンスコンテナのための修正のための好ましい場所（pop_back()とpush_back()）を作る。
2. priority_queueプリミティブはstd::make_heap（コンストラクタ）、std::pop_heap + container::pop_back（priority_queue::pop）上とstd::push_heap + container::push_backに基づいています（priority_queue::push）
3. pop_heapは、基礎となるストレージのフロントを取り、バックでそれを配置します、後でヒープ不変量を復元する。逆はpush_heapになります。
4. repeatedly pop the front to the back（最初に前面に最大で）max_heapにsort_heapをあろうこと、したがって
5. （既定の比較演算子である）lessに係る範囲をソート、max_heapの好ましい実施形態は、MAXを有することです要素wrtフロントのlessは、priority_queue::top（下位container::front）からアクセスします。
6. priority_queueがstd::lessのコンパレータがmax_heapを表すことが直感的であるかどうかは依然として議論することができます。コンパイラの引数を逆にすることでmin_heapと定義されている可能性があります（ただし、C++ 98バインダの場合は@ T.Cのコメントを参照してください）。 （私にとっては）1直感に反する結果がtop()が、その後最優先あなたが探している

Answer 2

、上部に最大の価値を保持することである、それはstd::greaterが最大ヒープの作成に使用されるべきであると私には見えませんpush_heap、およびは、max heapで動作します。つまり、デフォルトのコンパレータを使用すると、先頭の要素は最大です。したがって、最小ヒープを作成するには、less<T>の代わりにgreater<T>を使用する必要があります。

less操作で実装する方が簡単であるということは、最小ヒープの代わりに最大ヒープを使用すると考えられます。 C++では、lessは、すべてのSTLアルゴリズムの "デフォルト"コンパレータのような特権を持っています。 1つの比較操作（==以外）を実装する場合は、<にする必要があります。これは、priority_queue<T, C<T>, less<T>>が最大待ち行列を意味し、priority_queue<T, C<T>, greater<T>>が最小待ち行列を意味する、不運な不具合につながります。

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

Answer 3

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