un modo semplice per mantenere un heap minimo con stl?

Question

per struct definito dall'utente, come ho capito, è facile. Basta sovraccaricare l'operatore <. Tuttavia, per int/float, ecc., Devo veramente sovraccaricare l'operatore < per int? Ecco cosa ho provato:

 #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; 
     } 

i risultati sono:

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

ora pop_heap, push_heap non manterrà correttamente il min-heap? c'è un modo più semplice per raggiungere questo obiettivo? Grazie!

Modifica: scusate, non ho controllato attentamente il manuale. sì, passare il comp a pop_heap o push_heap dovrebbe fare il trucco. Tuttavia, cosa intendi, non dovrei usare un comparatore esterno? Se non è la strada giusta, qual è il modo comune per raggiungere questo obiettivo?

Answer 1

Non è necessario sovraccaricare operator < per int (non è possibile, in realtà). Se si utilizza un comparatore esterno, si dovrebbe passare lo stesso Comparator comp a pop_head.

* Edit: *

Come Ildjarn ha sottolineato, il vostro operatore di confronto non implementa una stretta relazione-deboli-ordinazione.

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

Answer 2

Utilizzare std::greater<int>() come il comparatore (a tutti make_heap, push_heap, pop_heap). I valori () sono importanti - std::greater<int> è una classe functor non una funzione, quindi è necessaria un'istanza.

Answer 3

Le risposte sono buone, quindi volevo solo aggiungere un piccolo esempio. Diciamo che avete il seguente array:

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

e si desidera creare un min heap. Il modo più rapido per farlo è utilizzare l'algoritmo make_heap. Tuttavia, ciò crea un max heap per impostazione predefinita. In altre parole, se si chiama:

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

A diventa un max heap. Per avere un min heap, d'altra parte, è necessario aggiungere un comparatore ma non è necessario implementarne uno. Invece chiamare il metodo come segue:

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

Questa chiamata renderà il vostro array a min heap.

PS: #include <algorithm> è necessario utilizzare std::make_heap. Le stesse operazioni si applicano anche allo vector.

HTH!