Определение функции сравнения для кучи Фибоначчи в бусте

Question

Определение функции сравнения для кучи Фибоначчи в бусте

Мне нужно использовать кучу Фибоначчи в моем проекте, и я пытаюсь использовать ее из библиотеки Boost. Но я не могу понять, как настроить пользовательскую функцию сравнения для произвольного типа данных. Мне нужно построить минимальную кучу для структурного узла, определенного следующим образом:

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

};

Я посмотрел документацию и там был класс сравнения. Но он не содержал никакого элемента. Подскажите пожалуйста, как настроить пользовательскую функцию сравнения.
Заранее спасибо.

5

boost c++fibonacci-heap templates

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

fibonacci_heap берет сравнение функтор, который эффективно struct или же class с оператором вызова функции — operator(), Я собираюсь упростить ваш node struct, но вы должны быть в состоянии использовать это с небольшими изменениями:

struct node
{
int id;

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

Теперь нам нужно определить класс, который сравнивает nodes. Это будет иметь 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";
}
}

8