フィボナッチヒープの比較関数を定義します。

Question

私のプロジェクトでフィボナッチヒープを使用する必要があり、ブーストライブラリから使用しようとしています。しかし、私はどのように任意のデータ型のユーザー定義の比較関数を設定するかを理解することはできません。私は次のように定義された構造体のノードの最小ヒープを構築する必要があります。

struct node 
{ 
    int id; 
    int weight; 
    struct node* next; 
       /* dist is a global array of integers */ 
    bool operator > (struct node b)         //Boost generates a Max-heap. What I need is a min-heap. 
      {return dist[id] < dist[b.id] ? 1:0 ;}    //That's why "<" is used for "operator >". 
    bool operator < (struct node b) 
      {return dist[id] > dist[b.id] ? 1:0 ;} 
    bool operator >=(struct node b) 
      {return dist[id] <= dist[b.id] ? 1:0 ;} 
    bool operator <=(struct node b) 
      {return dist[id] >= dist[b.id] ? 1:0 ;} 

    node() 
    { 
      id=0; 
      weight=0; 
      next=NULL; 
    } 

}; 

私は、ドキュメントを見上げると比較するクラスがありました。しかし、それはどんな要素も含んでいませんでした。ユーザー定義の比較機能の設定方法を教えてください。 ありがとうございます。 operator() -

fibonacci_heap

Answer 1

を効果的に関数呼び出し演算子でstruct又はclassある比較ファンクタをとります。私はあなたのnode構造体を簡素化するつもりですが、あなたは軽微な変更でこれを使用することができるはずです。

struct node 
{ 
    int id; 

    node(int i) 
     : id(i) 
    { } 
}; 

は今、私たちはnode Sを比較したクラスを定義する必要があります。これは、const参照で2つのノードを取るoperator()を持っている、と返されますbool次のように

struct compare_node 
{ 
    bool operator()(const node& n1, const node& n2) const 
    { 
     return n1.id > n2.id; 
    } 
}; 

私たちは、その後、私たちのヒープを宣言することができます。

boost::heap::fibonacci_heap<node, boost::heap::compare<compare_node>> heap; 

フル例：

#include <boost/heap/fibonacci_heap.hpp> 

#include <iostream> 

struct node 
{ 
    int id; 

    node(int i) 
     : id(i) 
    { } 
}; 

struct compare_node 
{ 
    bool operator()(const node& n1, const node& n2) const 
    { 
     return n1.id > n2.id; 
    } 
}; 

int main() 
{ 
    boost::heap::fibonacci_heap<node, boost::heap::compare<compare_node>> heap; 
    heap.push(node(3)); 
    heap.push(node(2)); 
    heap.push(node(1)); 

    for(const node& n : heap) { 
     std::cout << n.id << "\n"; 
    } 
}