Hi,
I put in 0,1,2,3,4 into a Fibonacci heap, manipulate some and get 0,2,4,1,25
back. With the relaxed heap I get 0,2,4,1,3 back, which is as expected with my
code. AFAIK this is due to a bug in the Fibonacci heap?
Anyway here is code adopted from the cvs (fibonacci_heap.cpp) that reproduces
the result on two different machines (intel/amd), where the programs are
compiled using g++ 4.0.4. Any help in clearing out this confusing result is
appreciated :)
#include <iostream>
#include <cstdlib>
#include <vector>
#include
#include
#include
#include
using namespace std;
using namespace boost;
int main(int argc, char *argv[])
{
typedef indirect_cmp ICmp;
unsigned current;
const unsigned N=5;
vector<unsigned> w(N);
ICmp cmp(&w[0], std::less<unsigned>());
Fibonacci_heap Q(N, cmp);
//relaxed_heap Q(N, cmp);
Q.push(0);
current=Q.top();
cout << current << " ";
Q.pop();
w[1]=180428938;
Q.push(1);
w[2]=84693088;
Q.push(2);
w[3]=168169277;
Q.push(3);
w[4]=171463691;
Q.push(4);
current = Q.top();
cout << current << " ";
Q.pop();
w[3]=164976049;
Q.update(3);
w[4]=59651664;
Q.update(4);
current = Q.top();
cout << current << " ";
Q.pop();
w[1]=71988538;
Q.update(1);
w[3]=118964142;
Q.update(3);
current = Q.top();
cout << current << " ";
Q.pop();
w[3]=42423833;
Q.update(3);
current = Q.top();
cout << current << " ";
Q.pop();
return EXIT_SUCCESS;
}
