C ++ Min Heap com tipo definido pelo usuário

Question

Estou tentando implementar uma pilha min em C ++ para um tipo de estrutura que eu criei. Criei um vetor do tipo, mas ele travou quando usei Make_Heap, o que é compreensível porque não sabe como comparar os itens na pilha. Como faço para criar um min-heap (ou seja, o elemento superior é sempre o menor da pilha) para um tipo de estrutura?

A estrutura está abaixo:

struct DOC{

int docid;
double rank;

};

Quero comparar as estruturas do DOC usando o membro da classificação. Como eu faria isso?

Tentei usar uma fila de prioridade com uma classe de comparador, mas isso também travou, e também parece bobo usar uma estrutura de dados que usa uma pilha como base subjacente quando o que eu realmente preciso é de uma pilha de qualquer maneira.

Muito obrigado, BSG

Answer 1

Adicione um operador de comparação:

struct DOC{

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

As estruturas quase sempre podem ter um construtor, então eu também acrescentaria:

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

para a estrutura também.

Answer 2

Basta criar seu próprio "Functor" para a comparação. Como você deseja um "Min Heap", sua função de comparação deve se comportar como o maior que o operador:

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

É importante que você sempre use a mesma função de comparação em outras operações de heap.