부스트에서 fibonacci 힙 비교 함수 정의

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() -

Answer 1

fibonacci_heap는 비교를 효과적으로 함수 호출 연산자와 struct 또는 class이다 펑을 걸린다. 나는 당신의 node 구조체를 단순화하는거야,하지만 당신은이 작은 수정을 사용할 수 있어야합니다 :

struct node 
{ 
    int id; 

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

지금, 우리는 node의 비교 클래스를 정의 할 필요가있다. 이것은 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"; 
    } 
}