Analysis of Java implementations of Fibonacci Heap
Some years ago, around 1997 or so, I wrote a Java implementation of the Fibonacci Heap data structure, as described in Introduction to Algorithms, by Cormen, Leisersen, Rivest, and Stein. A data structure such as the Fibonacci Heap is useful in graphing applications, such as the one I spent some time working on, GraphMaker.
Unfortunately, there were mistakes not only in my implementation, but in the pseudo-code published in the book. Due to the fact that my version was one of the first ever written in Java, and it was open source, it eventually spread to other open source software. A few months back, Jason Lenderman and John Sichi brought up an issue in the implementation via an email to me. In particular, John felt that the size of the degree array in the consolidate() method was too large. In fact, I had it set to the size of the heap, which meant the consolidate method had a running time of O(n). Oops, so much for the amortized O(log n) we were hoping for. After spending some time looking at other implementations, and studying the CLRS book, I realized that calculating the degree array size at all was a waste of time (n can never be greater than Integer.MAX_VALUE, and log base phi of that is 45). Terrific! The method was much faster now that it had an appropriately sized degree array.
Read full article from Analysis of Java implementations of Fibonacci Heap
No comments:
Post a Comment