Definieren der Vergleichsfunktion für Fibonacci Heap in Boost

Question

Ich muss Fibonacci-Heap in meinem Projekt verwenden und ich versuche, es aus Boost-Bibliothek zu verwenden. Aber ich kann nicht herausfinden, wie man eine benutzerdefinierte Vergleichsfunktion für einen beliebigen Datentyp einrichtet. Ich brauche einen Heap für struct min Knoten definiert zu konstruieren, wie folgt:

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

}; 

ich die Dokumentation nachgeschlagen, und es gab eine Vergleichs Klasse. Aber es enthielt kein Element. Bitte sagen Sie mir, wie Sie eine benutzerdefinierte Vergleichsfunktion einrichten. Vielen Dank im Voraus.

Answer 1

fibonacci_heap nimmt einen Vergleich Funktors, die effektiv ist ein struct oder class mit einem Funktionsaufruf Operator - operator(). Ich werde Ihre node Struktur vereinfachen, aber Sie sollten dies mit geringfügigen Änderungen verwenden können:

struct node 
{ 
    int id; 

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

Jetzt müssen wir eine Klasse definieren, die node s vergleicht. Dies wird eine operator() haben, die zwei Knoten, die durch konstante Referenz nimmt, und das Rück ein bool:

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

Wir können dann unsere Haufen erklären, wie folgt:

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

Ein vollständiges Beispiel:

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