बूस्ट

Question

में फाइबोनैकी ढेर के लिए फ़ंक्शन की तुलना परिभाषित करना मुझे अपनी परियोजना में फिबोनाची ढेर का उपयोग करने की आवश्यकता है और मैं इसे बूस्ट लाइब्रेरी से उपयोग करने का प्रयास कर रहा हूं। लेकिन मैं समझ नहीं सकता कि उपयोगकर्ता द्वारा मनमाने ढंग से डेटा प्रकार के लिए परिभाषित तुलना फ़ंक्शन को कैसे स्थापित किया जाए। मैं इस प्रकार struct नोड परिभाषित के लिए एक मिनट ढेर का निर्माण करने की जरूरत है:

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

}; 

मैं प्रलेखन ऊपर देखा और एक तुलना वर्ग नहीं था। लेकिन इसमें कोई तत्व नहीं था। कृपया मुझे बताएं कि उपयोगकर्ता परिभाषित तुलना फ़ंक्शन को कैसे सेट अप करें। अग्रिम धन्यवाद।

Answer 1

fibonacci_heap एक तुलना लेता functor है, जो प्रभावी रूप से एक struct या class एक समारोह कॉल ऑपरेटर के साथ है - operator()। मैं अपने node struct को आसान बनाने के लिए जा रहा हूँ, लेकिन आप मामूली संशोधनों के साथ इस का उपयोग करने में सक्षम होना चाहिए:

struct node 
{ 
    int id; 

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

अब, हम एक वर्ग है कि तुलना node रों को परिभाषित करने की जरूरत है। यह एक operator() कि स्थिरांक संदर्भ द्वारा 2 नोड्स लेता होगा, और वापस जाने के एक 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"; 
    } 
}