How to implement Prim's algorithm with a Fibonacci heap?

Question

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?

Solution 1

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:

1. My implementation of a Fibonacci heap.
2. 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!

Solution 2

Prim's algorithm selects the edge with the lowest weight between the group of vertexes already selected and the rest of the vertexes.
So to implement Prim's algorithm, you need a minimum heap. Each time you select an edge you add the new vertex to the group of vertexes you've already chosen, and all its adjacent edges go into the heap.
Then you choose the edge with the minimum value again from the heap.

So the time complexities we get are:
Fibonacci:
Choosing minimum edge = O(time of removing minimum) = O(log(E)) = O(log(V))
Inserting edges to heap = O(time of inserting item to heap) = 1

Min heap:
Choosing minimum edge = O(time of removing minimum from heap) = O(log(E)) = O(log(V))
Inserting edges to heap = O(time of inserting item to heap) = O(log(E)) = O(log(V))

(Remember that E =~ V^2 ... so log(E) == log(V^2) == 2Log(V) = O(log(V))

So, in total you have E inserts, and V minimum choosings (It's a tree in the end).

So in Min heap you'll get:

O(Vlog(V) + Elog(V)) == O(Elog(V))

And in Fibonacci heap you'll get:

O(Vlog(V) + E)

Solution 3

I implemented Dijkstra using Fibonacci heaps a few years ago, and the problem is pretty similar. Basically, the advantage of Fibonacci heaps is that it makes finding the minimum of a set a constant operation; so that's very appropriate for Prim and Dijkstra, where at each step you have to perform this operation.

Why it's good

The complexity of those algorithms using a binomial heap (which is the more "standard" way) is O(E * log V), because - roughly - you will try every edge (E), and for each of them you will either add the new vertex to your binomial heap (log V) or decrease its key (log V), and then have to find the minimum of your heap (another log V).

Instead, when you use a Fibonacci heap the cost of inserting a vertex or decreasing its key in your heap is constant so you only have a O(E) for that. BUT deleting a vertex is O(log V), so since in the end every vertex will be removed that adds a O(V * log V), for a total O(E + V * log V).

So if your graph is dense enough (eg E >> V), using a Fibonacci heap is better than a binomial heap.

How to

The idea is thus to use the Fibonacci heap to store all the vertices accessible from the subtree you already built, indexed by the weight of the smallest edge leading to it. If you understood the implementation or Prim's algorithm with using another data structure, there is no real difficulty in using a Fibonacci heap instead - just use the insert and deletemin methods of the heap as you would normally, and use the decreasekey method to update a vertex when you release an edge leading to it.

The only hard part is to implement the actual Fibonacci heap.

I can't give you all the implementation details here (that would take pages), but when I did mine I relied heavily on Introduction to algorithms (Cormen et al). If you don't have it yet but are interested in algorithms I highly recommend that you get a copy of it! It's language agnostic, and it provides detailed explanations about all the standards algorithms, as well as their proofs, and will definitely boost your knowledge and ability to use all of them, and design and prove new ones. This PDF (from the Wikipedia page you linked) provides some of the implementation details, but it's definitely not as clear as Introduction to algorithms.

I have a report and a presentation I wrote after doing that, that explain a bit how to proceed (for Dijkstra - see the end of the ppt for the Fibonacci heap functions in pseudo-code) but it's all in French... and my code is in Caml (and French) so I'm not sure if that helps!!! And if you can understand something of it please be indulgent, I was just starting programming so my coding skills were pretty poor at the time...

Comments

[Yochai Timmer]

Had a little calculation mistake... fixed

[Admin]

thanks. the best answer from my first day in SO to now. I will write it on my profile

[templatetypedef]

To whoever downvoted- can you please explain what your rationale is and what I can do to fix this?

[Gaminic]

Minor remark: I take it "Min heap" should be "Binary heap", or something similar. A Min heap is an abstract data structure; a Fibonacci heap can be used to implement a Min heap.

[Gaminic]

Practical note: Prim's Algorithm is better suited for using a Fibonacci heap than Dijkstra's algorithm. Dijkstra's performs loops of one extractMin and K decreaseKey (or Insert) operations; Prim's uses loops of K extractMin and K inserts (K being the average degree of nodes). On a Fibonacci heap, consecutive extractMin operations are close to free, while they are very expensive on other types of Heap.