C ++ min куча с пользовательским типом

Question

Я пытаюсь реализовать минимальную кучу в c ++ для типа структуры, которую я создал. Я создал вектор типа, но он потерпел крах, когда использовал на нем make_heap, что понятно, потому что он не знает, как сравнивать элементы в куче. Как создать мини-кучу (то есть верхний элемент всегда самый маленький в куче) для типа структуры?

Структура ниже:

struct DOC{

int docid;
double rank;

};

Я хочу сравнить структуры DOC, используя член ранга. Как бы я это сделал?

Я попытался использовать очередь приоритетов с классом компаратора, но он тоже потерпел крах, и также кажется глупым использовать структуру данных, которая использует кучу в качестве своей базовой основы, когда мне действительно нужно куча.

Большое спасибо, BSG

Answer 1

Просто создайте свой собственный "функтор" для сравнения. Поскольку вы хотите использовать «min heap», ваша функция сравнения должна вести себя как оператор «больше, чем»:

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

Важно, чтобы вы всегда использовали одну и ту же функцию сравнения в дальнейших операциях с кучей.

Answer 2

Добавьте оператор сравнения:

struct DOC{

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

Структуры почти всегда могут иметь конструктор, поэтому я бы также добавил:

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

в структуру.