簡単なヒープをstlで維持する簡単な方法は？

Question

私は理解しているように、ユーザー定義の構造体のために、それは簡単です。ちょうどオペレータ<をオーバーロードしてください。しかし、int/floatなどの場合、実際にはintのためにオペレータ<をオーバーロードする必要がありますか？ここ は、私が試したものです：

 #include <iostream> 
     #include <algorithm> 
     #include <vector> 
     using namespace std; 

     bool comp(const int& a, const int& b) 
     { 
      return a<b?false:true; 
     } 

     int main() 
     { 
     int myints[] = {10,20,30,5,15}; 
     vector<int> v(myints,myints+5); 
     vector<int>::iterator it; 
     make_heap(v.begin(), v.end(), comp); 
     cout << "initial min heap : " << v.front() << endl; 
     for (unsigned i=0; i<v.size(); i++) cout << " " << v[i]; 
     cout<<endl; 

     pop_heap (v.begin(),v.end()); 
     v.pop_back(); 
     for (unsigned i=0; i<v.size(); i++) cout << " " << v[i]; 
     cout<<endl; 
     } 

結果は以下のとおりです。

 initial min heap : 5 
     5 10 30 20 15 
     30 10 15 20 

今pop_heap、push_heapが正しく分ヒープを維持していないのだろうか？これを達成するための簡単な方法がありますか？ ありがとう！

編集： 申し訳ありませんが、私はマニュアルを慎重にチェックしませんでした。はい、pop_heapまたはpush_heapにコンプを渡すとそのトリックが行われます。しかし、どういう意味ですか、私は外部コンパレータを使うべきではありませんか？それが正しい方法でない場合、これを達成するための一般的な方法は何ですか？

Answer 1

operator <をintにオーバーロードする必要はありません（実際はできません）。外部コンパレータを使用する場合は、同じComparator compをpop_headにも渡す必要があります。

*編集：*

ildjarnが指摘したように、あなたの比較演算子は、厳密な弱順序関係を実装していません。

a < b ? false : true; --> a >= b 
b < a ? true : false; --> a > b 

Answer 2

（make_heap、push_heap、pop_heapのすべてに）コンパレータとして使用std::greater<int>()。 ()は重要です - std::greater<int>は関数ではなく関数クラスなので、そのインスタンスが必要です。

Answer 3

答えが良いので、ちょっとした例を追加したかっただけです。

array<int, 10> A{5,2,8,3,4,1,9,12,0,7}; 

とし、min heapを作成したいとします。最も簡単な方法は、アルゴリズムmake_heapを使用することです。ただし、既定ではmax heapが作成されます。言い換えれば、あなたが呼び出す場合：

make_heap(A.begin(), A.end()); 

Aがmax heapなります。一方、min heapを使用するには、コンパレータを追加する必要がありますが、コンパレータを実装する必要はありません。次のようにする代わりにメソッドを呼び出します。

make_heap(A.begin(), A.end(), greater<int>()); 

この呼び出しはあなたの配列min heapを行います。

PS：std::make_heapを使用するには、#include <algorithm>が必要です。 同じ操作がvectorにも適用されます。

HTH！