C++ montón mínimo con tipo definido por el usuario

Estoy tratando de implementar un montón mínimo en C++ para un tipo de estructura que he creado. Creé un vector del tipo, pero se bloqueó cuando utilicé make_heap, lo que es comprensible porque no sabe cómo comparar los elementos en el montón. ¿Cómo creo un min-heap (es decir, el elemento superior es siempre el más pequeño en el montón) para un tipo de estructura?C++ montón mínimo con tipo definido por el usuario

La estructura es a continuación:

struct DOC{ 

int docid; 
double rank; 

};

quiero comparar las estructuras DOC utilizando el miembro de rango. ¿Cómo haría esto?

Intenté utilizar una cola de prioridad con una clase de comparación, pero también se bloqueó, y también me parece tonto usar una estructura de datos que utiliza un montón como base cuando lo que realmente necesito es un montón.

Muchas gracias, BSG

Fuente

2010-04-04 bsg

¿Cuál es su definición de "se estrelló"? Seguramente, si no tiene functor de comparación u operador sellibitze

No, no lo hice, en realidad. Definitivamente no con la cola de prioridad, que tenía un operador sobrecargado definido, y tampoco creo con make_heap. Aunque podría ser que en el último caso obtuve un error de compilación. La primera vez, sin embargo, compiló bien, pero se estrelló en el tiempo de ejecución. – bsg

Si intenta utilizar make_heap con dos argumentos solamente, debe tener un operador sellibitze

Añadir un operador de comparación:

struct DOC{ 

    int docid; 
    double rank; 
    bool operator<(const DOC & d) const { 
     return rank < d.rank; 
    } 
};

estructuras pueden casi siempre útil tener un constructor, por lo que también añadiría:

DOC(int i, double r) : docid(i), rank(r) {]

a la estructura también

Fuente

2010-04-04 09:46:20

Por lo que puedo decir, esto llevaría a un "montón máximo". Pero él quiere un "montón mínimo" que requiera un functor que devuelva verdadero si y solo si el primer argumento es mayor que el segundo. – sellibitze

¡Muchas gracias! Terminé usando una cola de prioridad, porque tenía más de las funciones que necesitaba, pero creé un constructor y sobrecargué los operadores < and >, ¡y funcionó! – bsg

@bsg, si "funcionó" de esa manera, usted hizo la pregunta incorrecta y un "montón máximo" es lo que quería. Decídete. – sellibitze

Simplemente crea tu propio "functor" para la comparación. Puesto que usted quiere un "min heap" su función de comparación debe comportarse como el operador mayor que:

#include <iostream> 
#include <vector> 
#include <algorithm> 

struct doc { 
    double rank; 
    explicit doc(double r) : rank(r) {} 
}; 

struct doc_rank_greater_than { 
    bool operator()(doc const& a, doc const& b) const { 
     return a.rank > b.rank; 
    } 
}; 

int main() { 
    std::vector<doc> docvec; 
    docvec.push_back(doc(4)); 
    docvec.push_back(doc(3)); 
    docvec.push_back(doc(2)); 
    docvec.push_back(doc(1)); 
    std::make_heap(docvec.begin(),docvec.end(),doc_rank_greater_than()); 
    std::cout << docvec.front().rank << '\n'; 
}

Es importante que utilice siempre la misma función de comparación en otras operaciones de lixiviación.

Fuente

2010-04-04 10:08:28 sellibitze

C++ montón mínimo con tipo definido por el usuario

Respuesta

Cuestiones relacionadas