6

我正在尝试在 C++ 中为我创建的结构类型实现最小堆。我创建了一个该类型的向量，但是当我对其使用 make_heap 时它崩溃了，这是可以理解的，因为它不知道如何比较堆中的项目。如何为结构类型创建最小堆（即顶部元素始终是堆中最小的元素）？

结构如下：

struct DOC{

int docid;
double rank;

};

我想使用 rank 成员比较 DOC 结构。我该怎么做？

我尝试使用带有比较器类的优先级队列，但这也崩溃了，而且当我真正需要的是堆时，使用使用堆作为其底层基础的数据结构似乎也很愚蠢。

非常感谢，bsg

4

2 回答 2

7

只需创建自己的“函子”进行比较。由于您想要一个“最小堆”，因此您的比较函数应该表现得像大于运算符：

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

在进一步的堆操作中始终使用相同的比较函数很重要。

于 2010-04-04T10:08:28.987 回答
3

添加比较运算符：

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

结构也是如此。

于 2010-04-04T09:46:20.003 回答