CODEWITHSUNDEEP
data-structuresheapdijkstra
sv_jan5
sv_jan5

Reputation: 1573

What is the difference between binary, binomial, and Fibonacci heaps?

I want to know the basic difference between binary, binomial, and Fibonacci heaps and in which scenarios they are best to use. I am mainly concerned with their application in Dijkstra's algorithm that how it's Time complexity will vary depending on the type of the heap used?

Upvotes: 2

Views: 4468

Answers (1)

Arman
Arman

Reputation: 467

According to Wikipedia, a binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints complete binary tree and heap property. Note that heap property is all nodes are either greater or less than each of children.

Binomial heap is more complex than most of the binary heaps. However, it has excellent merge performance which bound to O(lg N) time. A binomial heap is consist of a list of binomial trees.

Before jumping into Fibonacci heaps, it's probably good to explore why we even need them in the first place. There are plenty of other types of heaps (binary heaps and binomial heaps, for example), so why do we need another one?

The main reason comes up in Dijkstra's algorithm and Prim's algorithm. Both of these graph algorithms work by maintaining a priority queue holding nodes with associated priorities. Interestingly, these algorithms rely on a heap operation called decrease-key that takes an entry already in the priority queue and then decreases its key (i.e. increases its priority). In fact, a lot of the runtime of these algorithms is explained by the number of times you have to call decrease-key. If we could build a data structure that optimized decrease-key, we could optimize the performance of these algorithms. In the case of the binary heap and binomial heap, decrease-key takes time O(log n), where n is the number of nodes in the priority queue. If we could drop that to O(1), then the time complexities of Dijkstra's algorithm and Prim's algorithm would drop from O(m log n) to (m + n log n), which is asymptotically faster than before. Therefore, it makes sense to try to build a data structure that supports decrease-key efficiently.

If you're interested in learning more about Fibonacci heaps, you may want to check out this two-part series of lecture slides. Part one introduces binomial heaps and shows how lazy binomial heaps work.Part two explores Fibonacci heaps. These slides go into more mathematical depth than what I've covered here.

Upvotes: 1

Related Questions