manera fácil de mantener un montón mínimo con stl?

Question

para la estructura definida por el usuario, como yo entiendo, es fácil. Solo sobrecargue el operador <. Sin embargo, para int/float, etc., ¿realmente necesito sobrecargar el operador < para int? Aquí es lo que he intentado:

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

los resultados son los siguientes:

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

ahora pop_heap, push_heap no mantendrá el min-heap correctamente? ¿hay alguna manera más fácil de lograr esto? Gracias!

Edit: lo siento, no revisé el manual con cuidado. sí, pasar comp a pop_heap o push_heap debería ser el truco. Sin embargo, ¿qué quiere decir con que no debería usar un comparador externo? Si no es el camino correcto, ¿cuál es la forma más común de lograr esto?

Answer 1

No necesita sobrecargar operator < para int (no puede, en realidad). Si usa un comparador externo, también debe pasar el mismo Comparator comp al pop_head.

* Editar: *

Como Ildjarn señaló, el operador de comparación no implementa una relación estricta débil de pedidos.

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

Answer 2

Uso std::greater<int>() como el comparador (a todos make_heap, push_heap, pop_heap). Los () son importantes: std::greater<int> es una clase de functor, no una función, por lo que necesita una instancia de la misma.

Answer 3

Las respuestas son buenas, así que solo quería agregar un pequeño ejemplo. Digamos que tiene la siguiente matriz:

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

y desea crear un min heap. La forma más rápida de hacerlo es usar el algoritmo make_heap. Sin embargo, eso crea un max heap por defecto. En otras palabras, si se llama:

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

A se convierte en un max heap. Para tener un min heap, por otro lado, debe agregar un comparador pero no necesita implementar uno. En su lugar, llame al método de la siguiente manera:

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

Esta llamada hará que su matriz a min heap.

PS: #include <algorithm> es necesario usar std::make_heap. Las mismas operaciones se aplican al vector también.

HTH!