On 7/19/06, Douglas Gregor
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
Hi Magnus, Doug, There was indeed a bug in the fibonacci heap code - the parent pointers weren't being updated in the make_child function. I just committed a fix for this to HEAD. I'd be grateful to hear from someone who has some heavy-duty code using the relaxed heap as to whether or not the fibonacci heap code works as a drop-in replacement now. Regards, Aaron