prosty sposób na utrzymanie sterty min z stl?

Question

dla zdefiniowanej przez użytkownika struct, jak rozumiem, jest to łatwe. Wystarczy przeciążyć operatora <. Jednak dla int/float itp., Czy naprawdę muszę przeciążać operatora < dla int? Oto, co starałem:

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

wyniki są następujące:

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

teraz pop_heap, push_heap nie utrzyma min sterty poprawnie? Czy jest jakiś łatwiejszy sposób, aby to osiągnąć? Dzięki!

Edytuj: Przepraszam, nie sprawdzałem dokładnie instrukcji. tak, przekazanie kompu do pop_heap lub push_heap powinno załatwić sprawę. Co masz na myśli, nie powinienem używać zewnętrznego komparatora? Jeśli nie jest to właściwa droga, jaki jest wspólny sposób, aby to osiągnąć?

Answer 1

Nie należy przeciążać operator < dla int (w rzeczywistości nie można tego zrobić). Jeśli korzystasz z komparatora zewnętrznego, powinieneś również przekazać ten sam numer Comparator comp do pop_head.

* Edycja: *

Jak Ildjarn wskazał, operator porównania nie realizuje relację ścisłe-słaby zamawiania.

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

Answer 2

Zastosowanie std::greater<int>() jako komparator (do wszystkich make_heap, push_heap, pop_heap). Ważne są: () - klasa functor nie jest funkcją, więc potrzebujesz jej instancji.

Answer 3

Odpowiedzi są dobre, więc chciałem dodać mały przykład. Załóżmy, że masz następującą tablicę:

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

i chcesz utworzyć min heap. Najszybszym sposobem jest użycie algorytmu make_heap. Jednak domyślnie tworzy to max heap. Innymi słowy, jeśli zadzwonisz:

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

A staje się max heap. Z drugiej strony, aby mieć min heap, trzeba dodać komparator, ale nie trzeba go implementować. Zamiast wywołać metodę w następujący sposób:

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

Ta rozmowa sprawi, że tablica min heap.

PS: #include <algorithm> jest konieczne do korzystania z std::make_heap. Te same operacje dotyczą również modelu vector.

HTH!