Boynun içinde fibonacci yığınını karşılaştırma işlevini tanımla

Question

Projemde Fibonacci yığınını kullanmalıyım ve bunu destek kitaplığından kullanmaya çalışıyorum. Ancak, rasgele veri türü için kullanıcı tanımlı karşılaştırma işlevinin nasıl kurulacağını anlayamıyorum. Aşağıdaki gibi tanımlanan yapı düğüm için bir dakika yığın oluşturmak için gereken:

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

}; 

I belgeleri aranır ve bir karşılaştırma sınıf yoktu. Ama hiçbir şey içermiyordu. Lütfen kullanıcı tanımlı karşılaştırma fonksiyonunu nasıl kurduğumu söyle. Önceden teşekkür ederiz. operator() -

Answer 1

fibonacci_heap bir karşılaştırması bir işlev arama operatörü ile struct veya class olan functor alır. Ben senin node yapı basitleştirmek için gidiyorum, ama bu küçük değişiklikler yapılarak kullanmak mümkün olmalıdır:

struct node 
{ 
    int id; 

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

Şimdi, node s karşılaştıran bir sınıf tanımlamak gerekir. Bu const referans olarak 2 düğümlerini alır bir operator() var ve dönecektir bir bool şu şekildedir:

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

Sonra bizim yığın ilan edebilir:

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

Tam örnek:

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