C ++ min mucchio con tipo definito dall'utente

Question

Sto cercando di implementare un min heap in C ++ per un tipo struct che ho creato. Ho creato un vettore di tipo, ma è caduto quando ho usato make_heap su di esso, il che è comprensibile, perché non sa come mettere a confronto gli elementi nel mucchio. Come si crea un min-heap (cioè, l'elemento superiore è sempre il più piccolo nel mucchio) per un tipo struct?

La struct è qui sotto:

struct DOC{

int docid;
double rank;

};

voglio mettere a confronto le strutture DOC utilizzando il membro rango. Come faccio a fare questo?

Ho provato ad utilizzare una coda di priorità con una classe di confronto, ma anche caduto, e sembra anche stupido utilizzare una struttura di dati che utilizza un mucchio come base sottostante quando ciò che realmente serve è un mucchio comunque.

La ringrazio molto, BSG

Answer 1

Aggiungi un operatore di confronto:

struct DOC{

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

Le strutture possono quasi sempre utilmente avere un costruttore, quindi vorrei anche aggiungere:

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

per la struct pure.

Answer 2

È sufficiente creare il proprio "funtore" per il confronto. Dal momento che si desidera un "min mucchio" la funzione di confronto deve comportarsi come il più grande di operatore:

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

E 'importante utilizzare sempre la stessa funzione di confronto in ulteriori operazioni di heap.