Real world applications of Binary heaps and Fibonacci Heaps

algorithm data-structures binary-heap fibonacci-heap
softwarematter picture softwarematter · Sep 22, 2010 · Viewed 21k times · Source

What are the real world applications of Fibonacci heaps and binary heaps? It'd be great if you could share some instance when you used it to solve a problem.

Edit: Added binary heaps also. Curious to know.

Answer

Peter Alexander picture Peter Alexander · Sep 22, 2010

You would rarely use one in real life. I believe the purpose of the Fibonacci heap was to improve the asymptotic running time of Dijkstra's algorithm. It might give you an improvement for very, very large inputs, but most of the time, a simple binary heap is all you need.

From Wiki:

Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular delete and delete minimum have linear running time in the worst case). For this reason Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.

The binary heap is a data structure that can be used to quickly find the maximum (or minimum) value in a set of values. It's used in Dijkstra's algorithm (shortest path), Prim's algorithm (minimum spanning tree) and Huffman encoding (data compression).

Related questions

Max-Heapify A Binary Tree

This is one of the interview questions I recently came across. Given the root address of a complete or almost complete binary tree, we have to write a function to convert the tree to a max-heap. There are no arrays …

Read More
Finding last element of a binary heap

quoting Wikipedia: It is perfectly acceptable to use a traditional binary tree data structure to implement a binary heap. There is an issue with finding the adjacent element on the last level on the binary heap when adding an element …

Read More
What is the difference between binary heaps and binomial heaps?

I need to know the main difference between binary and binomial heaps regardless of the their structure difference that binary heaps can have only two child (tree representation) and binomial heaps can have any number of children. I am actually …

Read More