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

Question

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

Структура приведена ниже:

struct DOC{

int docid;
double rank;

};

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

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

Большое вам спасибо, bsg

Answer 1

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

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) {]

в структуру, а также.

Answer 2

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

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

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