C ++最小堆与用户定义型

Question

我试图实现在C + +最小堆一个结构类型我创建。我创建的类型的载体，但是当我用make_heap就可以了，这是可以理解的，因为它不知道如何比较堆中项目坠毁。如何创建一个最小堆（即，顶部元件总是在堆最小的一个），用于结构类型？

在结构低于：

struct DOC{

int docid;
double rank;

};

我想比较使用秩构件的DOC结构。我会怎么做呢？

我试图用一个优先级队列有比较级，但也应声，而且似乎也傻采用利用堆作为其底层基础数据结构，当我真正需要的是一个堆反正。

非常感谢你， 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

只需创建比较自己的“仿函数”。既然你想要一个“最小堆”你的比较函数应该表现得像大于运算符：

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

这始终使用相同的比较功能进一步堆操作是很重要的。