Re: [Boost-users] The fibonacci heap is behaving strange

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-07-19 14:15:07

On Jul 19, 2006, at 4:28 AM, Magnus Ekdahl wrote:
> 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  :)

Oh, yuck. The Fibonacci heap code has been sitting in "pending" for  
years; I never came forward for real acceptance as a Boost library.

Actually, back when I was working on the relaxed heap code, I'd run  
into similar problems with the Fibonacci heap. I never bothered to  
debug the issue, because relaxed heaps are "supposed" to be faster.

So, I don't have an answer for you, other than perhaps "don't use the  
Fibonacci" heap. We might just deprecate it for the upcoming Boost  
release and remove it thereafter, unless someone is willing to fix it  
and bring it forward. Sorry :(

        Doug