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

From: Magnus Ekdahl (maguno_at_[hidden])
Date: 2006-07-20 07:01:07

Douglas Gregor wrote:
> 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
...

This answer works for me. I'll just use the relaxed heap then.  :)

/Magnus Ekdahl