6

作成した構造体型の最小ヒープをC++で実装しようとしています。このタイプのベクトルを作成しましたが、make_heapを使用するとクラッシュしました。これは、ヒープ内のアイテムを比較する方法がわからないため、理解できます。構造体タイプの最小ヒープ(つまり、最上位の要素は常にヒープ内で最小の要素)を作成するにはどうすればよいですか?

構造体は以下のとおりです。

struct DOC{

int docid;
double 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 に答える