Definizione della funzione di confronto per heap di fibonacci in boost

Question

Ho bisogno di utilizzare l'heap di Fibonacci nel mio progetto e sto cercando di usarlo dalla libreria boost. Ma non riesco a capire come impostare una funzione di confronto definita dall'utente per tipo di dati arbitrario. Ho bisogno di costruire un mucchio min per il nodo struct definiti come segue:

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

}; 

ho guardato la documentazione e c'era una classe confrontare. Ma non conteneva alcun elemento. Per favore dimmi come impostare una funzione di confronto definita dall'utente. Grazie in anticipo.

Answer 1

fibonacci_heap guadagnato un confronto functor, che è effettivamente un struct o class con un operatore di chiamata di funzione - operator(). Ho intenzione di semplificare il vostro node struct, ma si dovrebbe essere in grado di utilizzare questo con piccole modifiche:

struct node 
{ 
    int id; 

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

Ora, abbiamo bisogno di definire una classe che mette a confronto node s. Ciò avrà un operator() che prende 2 nodi per riferimento const, e restituire un bool:

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

Possiamo quindi dichiarare la nostra mucchio come segue:

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

Un esempio completo:

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