Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Real world applications of Binary heaps and Fibonacci Heaps [closed]

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.

like image 767
softwarematter Avatar asked Sep 22 '10 09:09

softwarematter


People also ask

What are the applications of binary heap?

Following are some uses other than Heapsort. Priority Queues: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomoial Heap and Fibonacci Heap are variations of Binary Heap.

What is Fibonacci heap explain with example?

In Fibonacci Heap, trees can have any shape even all trees can be single nodes (This is unlike Binomial Heap where every tree has to be Binomial Tree). Below is an example Fibonacci Heap taken from here. Fibonacci Heap maintains a pointer to minimum value (which is root of a tree).

What are heaps best used for?

Heaps are used in many famous algorithms such as Dijkstra's algorithm for finding the shortest path, the heap sort sorting algorithm, implementing priority queues, and more. Essentially, heaps are the data structure you want to use when you want to be able to access the maximum or minimum element very quickly.

Is Fibonacci heap faster than binary heap?

Fibonacci heaps also outperform binary heaps on insertion and merging (both amortized constant-time for Fibonacci heaps).


Video Answer


2 Answers

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).

like image 132
Peter Alexander Avatar answered Sep 23 '22 22:09

Peter Alexander


Can't say about the fibonacci heaps but binary heaps are used in the priority queues. Priority queues are widely used in the real systems.

One known example is process scheduling in the kernel. The highest priority process is taken first.

I have used the priority queues in the partitioning of the sets. The set which has the maximum members was to be taken first for the partitioning.

like image 20
Manoj R Avatar answered Sep 23 '22 22:09

Manoj R