Fibonacci Heap

Fibonacci heap is a heap data-structure that mimics the fibonacci sequence. It is very interesting to use to find Minimum Spanning Tree and single source shortest path, like in Dijkstra algorithm.

As it's somehow complex to implement, it's not very used in practice.

Pointers

Each node has the following pointers:

• 1 to the parent
• 1 to any one of the children
• 2 to the direct siblings (or itself if it is an only child)
• Degrees, i.e. the number of its direct children
• Mark, i.e. does this node has lost a child

We also keep track of

• total number of nodes in the heap
• minimum node value in the heap

Complexity

Time complexity

• Insert node: $\mathrm{\Theta }(1)$
• Find minimum: $\mathrm{\Theta }(1)$
• Delete minimum: $O(\log n)$ (amortized)
• Decrease key: $\mathrm{\Theta }(1)$ (amortized)

Note: amortized is the average time over a sequence of operation

Resources

• Fibonacci Heaps in 6 minutes - Intro – Youtube
• Fibonacci Heaps in 6 minutes - Insert and Union – Youtube
• Fibonacci Heaps in 6 minutes - Extract min – Youtube
• Fibonacci Heaps in 6 minutes - Decreases key – Youtube