Уменьшить работу в куче Фибоначчи, повысить
Я пытаюсь использовать в своей реализации кучу Фибоначчи от boost, но моя программа падает, когда я вызываю функцию lower, вот пример (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, который неинициализирован.
Проще, правильно, пример:
#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]);
}
Другие решения