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