C ++ min Heap mit benutzerdefinierten Typ

Question

Ich versuche, einen min-Heap in C ++ für einen Strukturtyp zu implementieren, die ich schaffte. Ich habe einen Vektor vom Typ, aber es stürzt ab, wenn ich darauf verwendet make_heap, was verständlich ist, weil sie nicht weiß, wie die Elemente in dem Heap zu vergleichen. Wie erstelle ich einen min-Heap (das heißt, das obere Element ist immer die kleinste in dem Heap) für einen Strukturtyp?

Die Struktur ist unter:

struct DOC{

int docid;
double rank;

};

Ich mag die DOC-Strukturen mit dem Rang Mitglied vergleichen. Wie würde ich das tun?

Ich habe versucht, eine Prioritätswarteschlange mit einer Komparator-Klasse, aber das auch abgestürzt, und es scheint auch albern, eine Datenstruktur zu verwenden, die einen Haufen als zugrunde liegende Basis verwendet, wenn, was mir wirklich braucht ein Haufen sowieso.

Vielen Dank, bsg

Answer 1

Fügen Sie einen Vergleichsoperator:

struct DOC{

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

können Strukturen fast immer sinnvollerweise einen Konstruktor haben, so würde ich auch hinzufügen:

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

auf die Struktur als auch.

Answer 2

Sie einfach Ihren eigenen „Funktor“ für den Vergleich erstellen. Da Sie einen „min heap“ Ihre Vergleichsfunktion wie die größer ist als Operator verhalten soll wollen:

#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 ist wichtig, dass Sie immer die gleiche Vergleichsfunktion in weiteren Heap-Operationen verwenden.