heap min C++ con tipo definito dall'utente

Sto cercando di implementare un heap minimo in C++ per un tipo di struct che ho creato. Ho creato un vettore del tipo, ma si è bloccato quando ho usato make_heap su di esso, il che è comprensibile perché non sa come confrontare gli elementi nell'heap. Come posso creare un min-heap (ovvero, l'elemento superiore è sempre il più piccolo nell'heap) per un tipo di struct?heap min C++ con tipo definito dall'utente

La struct è qui sotto:

struct DOC{ 

int docid; 
double rank; 

};

voglio mettere a confronto le strutture DOC utilizzando il membro rango. Come lo farei?

Ho provato a utilizzare una coda di priorità con una classe di confronto, ma anche questo si è bloccato, e sembra anche sciocco utilizzare una struttura dati che utilizza un heap come base di partenza quando quello che mi serve è un heap comunque.

La ringrazio molto, BSG

fonte

2010-04-04 bsg

qual è la tua definizione di "arresto anomalo"? Sicuramente, se non si dispone di alcuna funzione di comparatore o operatore sellibitze

No, non l'ho fatto, in realtà. Sicuramente non con la coda di priorità, che aveva definito un operatore sovraccarico, e non penso nemmeno con make_heap. Anche se potrebbe essere che in quest'ultimo caso ho avuto un errore di compilazione. La prima volta, tuttavia, è stata compilata correttamente ma si è bloccata in fase di esecuzione. – bsg

Se si tenta di utilizzare make_heap solo con due argomenti, è necessario un operatore sellibitze

Aggiungi un operatore di confronto:

struct DOC{ 

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

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

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

a la struttura pure.

fonte

2010-04-04 09:46:20

Per quanto posso dire, ciò comporterebbe un "max heap". Ma vuole un "min heap" che richiede un funtore che ritorna vero se e solo se il primo argomento è maggiore del secondo. – sellibitze

Grazie mille! Ho finito per usare una coda di priorità, perché aveva più funzioni di cui avevo bisogno, ma ho creato un costruttore e sovraccaricato gli operatori < and > come hai mostrato e ha funzionato! – bsg

@bsg, se "ha funzionato" in questo modo, hai posto la domanda sbagliata e un "max heap" è quello che volevi. Deciditi. – sellibitze

Basta 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.

fonte

2010-04-04 10:08:28 sellibitze

heap min C++ con tipo definito dall'utente

risposta

Problemi correlati