我需要在我的项目中使用 Fibonacci 堆,我正在尝试从 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;
}
};
我查了一下文档,有一个比较类。但它不包含任何元素。请告诉我如何设置用户定义的比较功能。 提前谢谢你。
最佳答案
fibonacci_heap
采用比较 functor,它实际上是一个带有函数调用运算符的 struct
或 class
- 运算符()
。我将简化您的 node
结构,但您应该能够通过较小的修改来使用它:
struct node
{
int id;
node(int i)
: id(i)
{ }
};
现在,我们需要定义一个比较节点
的类。这将有一个 operator()
,它通过 const 引用获取 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";
}
}
关于c++ - 在boost中为斐波那契堆定义比较函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16705894/