Fibonacci heap is a collection of trees that follow two main properties min heap and max heap.
Min heap is the property where a given node is always smaller than the child node and the key of the root node is the smallest among other nodes
Max heap is the property where a given node is always greater than the child node and the key of the root node is the largest among other nodes
Nodes in the Fibonacci heap can have more than two children or none.
Properties of a Fibonacci Heap
It is a set of min heap-ordered trees where the parent is always smaller than the children.
The minimum element node maintains a pointer.
Consists of a set of marked nodes.
Trees within a Fibonacci are rooted but unordered.
The roots of all trees are linked together for fast access. The child nodes of a particular parent are connected through a circular doubly linked list. This is mainly because of the minimal time used to delete a node from the tree and concatenation of the lists.
Operations in Fibonacci Heap
Insertion: inserting a node into an already existing heap.
Find min: minimum element is given by the min pointer.
Union: concatenating two Fibonacci heaps.
Extract Min: the node with the minimum value is removed from the heap and the tree is re-adjusted.
Fibonacci Application
Fibonacci heaps are used to improve the running time of Dijkstra's algorithm. Dijkstra's algorithm is an algorithm that finds the shortest paths from the starting source to other points in the graph.