5

我需要在我的项目中使用斐波那契堆，我正在尝试从 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;
    }

};

我查阅了文档，有一个比较类。但它不包含任何元素。请告诉我如何设置用户定义的比较功能。先感谢您。

4

1 回答 1

9

fibonacci_heap接受一个比较函子，它实际上是一个struct或class带有一个函数调用运算符 - operator()。我将简化您的node结构，但您应该能够通过少量修改来使用它：

struct node
{
    int id;

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

现在，我们需要定义一个比较nodes 的类。这将operator()通过 const 引用获取 2 个节点，并返回 a 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";
    }
}
于 2013-05-23T05:05:14.900 回答