Fibonacci Heap Issue

Question

I've been working on a Fibonacci Heap implementation in Java for about a week now. It's the implementation based off of the CLRS book.

I wanted to see if I would get any performance boost using it in a side project I'm working on compared to Java's default PriorityQueue. [The default implementation in Java is array based, so much more local. It may still outperform the F-Heap despite higher bounds in complexity].

My issue seems to stem from the consolidate part of the heap after removing the min element. I keep getting arrayindexoutofboundsexceptions thrown. Specifically in the while loop, when it is consolidating all nodes that have the same degree. It is exceeding the bounds set by the D() function.

So either my D() function is wrong, which, I don't think it is, or something else is happening. Most likely side effect related.

The code is located here. I've been trying to debug this for about week with now luck. Am I missing something obvious?

Answer 1

I know this is not what you're asking. But if hunting for performance, you're using the wrong language.

Answer 2

You will need to check the analysis since I'm not sure if the upper bound of the node degree should not be the floor. In your D function, your cast to int is truncating the decimal portion. Changing this to rounding seems to clear up the index out of bounds error.

There seems to be an additional problem though. I didn't track down what conditions but child lists can end up not having a sentinal set. This leads to an infinite loop in removeMin when looping through the child list since they are circular.