定义比较功能的升压斐波那契堆 [英] Defining compare function for fibonacci heap in boost

问题描述

我需要使用斐波那契堆在我的项目，我想从Boost库使用它。但我想不出如何设置任意数据类型的用户定义的比较功能。我需要构造一个最小堆的定义结构节点如下：

I need to use Fibonacci heap in my project and I am trying to use it from boost library. But I cannot figure out how to set up a user defined compare function for arbitrary data type. I need to construct a min heap for struct node defined as follows:

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

};

我抬起头的文件，并有一个比较类。但它不包含任何元素。请告诉我如何设置比较定义功能的用户。
谢谢你在前进。

I looked up the documentation and there was a compare class. But it did not contain any element. Please tell me how to set up a user defined compare function. Thank you in advance.

推荐答案

fibonacci_heap 需要比较的仿的，这实际上是一个结构或类用函数调用运算符 - 操作符（）。我要简化你的节点结构，但你应该能够稍作修改使用：

fibonacci_heap takes a comparison functor, which is effectively a struct or class with a function call operator - operator(). I'm going to simplify your node struct, but you should be able to use this with minor modifications:

struct node
{
    int id;

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

现在，我们需要定义一个比较类节点秒。这将有一个操作符（）通过const引用需要2个节点，并返回一个布尔：

Now, we need to define a class that compares nodes. This will have an operator() that takes 2 nodes by const reference, and return a bool:

struct compare_node
{
    bool operator()(const node& n1, const node& n2) const
    {
        return n1.id > n2.id;
    }
};

我们就可以宣布，我们堆如下：

We can then declare our heap as follows:

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

这篇关于定义比较功能的升压斐波那契堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！