Sterty min. C++ z typem zdefiniowanym przez użytkownika

Question

Próbuję zaimplementować stertę min w C++ dla typu struct, który utworzyłem. Stworzyłem wektor typu, ale rozbił się, gdy użyłem make_heap na nim, co jest zrozumiałe, ponieważ nie wie, jak porównać elementy w stercie. Jak utworzyć min-stertę (czyli najwyższy element zawsze jest najmniejszy w sterty) dla typu struktury?

Struct jest poniżej:

struct DOC{ 

int docid; 
double rank; 

}; 

Chcę porównać struktur DOC za pomocą członu rank. Jak to zrobić?

Próbowałem użyć kolejki priorytetowej z klasą komparatora, ale to również się zawiesiło, a także wydaje się głupio używać struktury danych, która wykorzystuje stertę jako podstawę, gdy tak naprawdę potrzebuję sterty.

Dziękuję bardzo, BSG

Answer 1

Dodaj operatora porównania:

struct DOC{ 

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

Structures może prawie zawsze z pożytkiem mieć konstruktora, więc chciałbym również dodać:

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

do także struktura.

Answer 2

Po prostu stwórz własny "funktor" dla porównania. Skoro chcesz „min heap” czynność porównanie powinno zachowywać się jak większa niż operatora:

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

Ważne jest, aby zawsze używać tej samej funkcji porównania w dalszych operacjach sterty.