The fibonacci heap is behaving strange

19 Jul 2006

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

Magnus Ekdahl

Douglas Gregor

Magnus Ekdahl

Aaron Windsor

David Abrahams

Douglas Gregor

tags

participants (4)