Fibonacci Heap

Overview

Originally developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987, the name Fibonacci heap comes from Fibonacci numbers which are used in the running time analysis.

Concept

The Fibonacci heap is a heap consisting of a collection of trees which satisfy the minimum-heap property.

Algorithmic Complexity

Fibonacci heaps offers better amortized running time than binomial and binary heaps.

Big-O

HeapsHeapifyFind MaxExtract MaxIncrease KeyInsertDeleteMerge
Fibonacci Heap-O(1)O(log(n))*O(1)*O(1)O(log(n))*O(1)

Implementation

Java Implementation

Coming soon!

References

Wikipedia: Fibonacci heap