c++ - heaps - ¿Una forma fácil de mantener un montón de minutos con stl?

min heap java

Question

Para la estructura definida por el usuario, como entiendo, es fácil. Solo sobrecargue el operador <. Sin embargo, para int / float, etc., ¿realmente necesito sobrecargar al operador <para int? Esto es lo que intenté:

       #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:

        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 hacer el truco. Sin embargo, ¿qué quiere decir con que no debería usar un comparador externo? Si no es la forma correcta, ¿cuál es la forma común de lograr esto?

Answer 1

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

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

y quieres 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 de forma predeterminada. En otras palabras, si llamas:

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

A convierte en un max heap . Para tener un min heap , por otro lado, necesita 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 tu matriz sea un min heap .

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

HTH!

Answer 2

No debería tener que sobrecargar el operator < para int (no puede, en realidad). Si usa un comparador externo, también debería pasar la misma pop_head Comparator comp a pop_head .

* Edición: *

Como señaló ildjarn, su operador de comparación no implementa una relación de ordenamiento débil-estricto.

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

Answer 3

Use std::greater<int>() como comparador (para todos make_heap , push_heap , pop_heap ). Los () son importantes - std::greater<int> es una clase de funtor no una función, por lo que necesita una instancia de ella.