How to implement Prim's algorithm with a Fibonacci heap?
I know Prim's algorithm and I know its implementation but always I skip a part that I want to ask now. It was written that Prim's algorithm implementation with Fibonacci heap is O(E + V log(V)) and my question is:
- what is a Fibonacci heap in brief?
- How is it implemented? And
- How can you implement Prim's algorithm with a Fibonacci heap?
Answer
A Fibonacci heap is a fairly complex priority queue that has excellent amoritzed asymptotic behavior on all its operations - insertion, find-min, and decrease-key all run in O(1) amortized time, while delete and extract-min run in amortized O(lg n) time. If you want a good reference on the subject, I strongly recommend picking up a copy of "Introduction to Algorithms, 2nd Edition" by CLRS and reading the chapter on it. It's remarkably well-written and very illustrative. The original paper on Fibonacci heaps by Fredman and Tarjan is available online, and you might want to check it out. It's dense, but gives a good treatment of the material.
If you'd like to see an implementation of Fibonacci heaps and Prim's algorithm, I have to give a shameless plug for my own implementations:
- My implementation of a Fibonacci heap.
- My implementation of Prim's algorithm using a Fibonacci heap.
The comments in both of these implementations should provide a pretty good description of how they work; let me know if there's anything I can do to clarify!