减少斐波那契堆中的操作，提高 [英] Decrease operation in fibonacci heap, boost

问题描述

我试图在实现中使用boost的斐波那契堆，但程序崩溃，当我调用reduce函数时，此示例(W是一个简单的类):

struct heap_data
{
    boost::heap::fibonacci_heap<heap_data>::handle_type handle;
    W* payload;

    heap_data(W* w)
    {
        payload = w;
    }

    bool operator<(heap_data const & rhs) const
    {
        return payload->get_key() < rhs.payload->get_key();
    }
};



int main()
{
    boost::heap::fibonacci_heap<heap_data> heap;

    vector<heap_data> A;

    for (int i = 0; i < 10; i++)
    {
        W* w = new W(i, i + 3);
        heap_data f(w);

        A.push_back(f);

        boost::heap::fibonacci_heap<heap_data>::handle_type handle = heap.push(f);
        (*handle).handle = handle; // store handle in node
    }

    A[5].payload->decr();

    heap.decrease(A[5].handle);

    return 0;
}

解决方案

问题很简单.

您有两个 容器(向量A和堆heap).

堆包含向量中数据的副本:

A.push_back(f);                    // copies f!
handle_type handle = heap.push(f); // copies f again!

您只能在堆中的副本上设置句柄:

(*handle).handle = handle; // store handle in the heap node only

因此，在临时f和向量A的元素中，handle的值是不确定的(您只是没有给它任何值).

因此，当您进行

heap.decrease(A[5].handle);

您调用未定义行为，因为您依赖于未初始化的A[5].handle值.

简单，正确的示例:

在Coliru上直播

#include <boost/heap/fibonacci_heap.hpp>
#include <boost/tuple/tuple_comparison.hpp>

struct W {
    int a;
    int b;

    W(int a, int b) : a(a), b(b) { }

    boost::tuple<int const&, int const&> get_key() const { return boost::tie(a, b); }

    void decr() { b?a:--a, b?--b:b; }
};

struct heap_data;
using Heap = boost::heap::fibonacci_heap<heap_data>;

struct heap_data
{
    W payload;
    Heap::handle_type handle;

    heap_data(W w) : payload(w), handle() {}

    bool operator<(heap_data const & rhs) const {
        return payload.get_key() < rhs.payload.get_key();
    }
};

#include <vector>
#include <iostream>

int main()
{
    Heap heap;

    std::vector<Heap::handle_type> handles;

    for (int i = 0; i < 10; i++)
    {
        Heap::handle_type h = heap.push(W { i, i + 3 });
        handles.push_back(h);
        (*h).handle = h;
    }

    (*handles[5]).payload.decr();
    heap.decrease(handles[5]);
}

I'm trying to use in my implementation the fibonacci heap from boost but my program crashes, when I calling decrease function, this the example (W is a simple class):

struct heap_data
{
    boost::heap::fibonacci_heap<heap_data>::handle_type handle;
    W* payload;

    heap_data(W* w)
    {
        payload = w;
    }

    bool operator<(heap_data const & rhs) const
    {
        return payload->get_key() < rhs.payload->get_key();
    }
};



int main()
{
    boost::heap::fibonacci_heap<heap_data> heap;

    vector<heap_data> A;

    for (int i = 0; i < 10; i++)
    {
        W* w = new W(i, i + 3);
        heap_data f(w);

        A.push_back(f);

        boost::heap::fibonacci_heap<heap_data>::handle_type handle = heap.push(f);
        (*handle).handle = handle; // store handle in node
    }

    A[5].payload->decr();

    heap.decrease(A[5].handle);

    return 0;
}

解决方案

The problem is quite trivial.

You have two containers (vector A and heap heap).

The heap contains copies of the data in the vector:

A.push_back(f);                    // copies f!
handle_type handle = heap.push(f); // copies f again!

You set the handle only on the copy in the heap:

(*handle).handle = handle; // store handle in the heap node only

Hence, in the temporary f and the vector A's elements, the value of handle is indeterminate (you just didn't give it any value).

Therefore when you do

heap.decrease(A[5].handle);

you invoke Undefined Behaviour because you depend on the value of A[5].handle, which is uninitialized.

Simpler, correct, example:

Live On Coliru

#include <boost/heap/fibonacci_heap.hpp>
#include <boost/tuple/tuple_comparison.hpp>

struct W {
    int a;
    int b;

    W(int a, int b) : a(a), b(b) { }

    boost::tuple<int const&, int const&> get_key() const { return boost::tie(a, b); }

    void decr() { b?a:--a, b?--b:b; }
};

struct heap_data;
using Heap = boost::heap::fibonacci_heap<heap_data>;

struct heap_data
{
    W payload;
    Heap::handle_type handle;

    heap_data(W w) : payload(w), handle() {}

    bool operator<(heap_data const & rhs) const {
        return payload.get_key() < rhs.payload.get_key();
    }
};

#include <vector>
#include <iostream>

int main()
{
    Heap heap;

    std::vector<Heap::handle_type> handles;

    for (int i = 0; i < 10; i++)
    {
        Heap::handle_type h = heap.push(W { i, i + 3 });
        handles.push_back(h);
        (*h).handle = h;
    }

    (*handles[5]).payload.decr();
    heap.decrease(handles[5]);
}

这篇关于减少斐波那契堆中的操作，提高的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！