124. Introducing the Fibonacci Heap data structure
A Fibonacci Heap is a flavor of Binomial Heap with excellent performance in amortized time for operations such as insert, extract minimum, and merge. It is an optimal choice for implementing priority queues. A Fibonacci Heap is made of trees, and each tree has a single root and multiple children arranged in a heap-ordered fashion. The root node with the smallest key is always placed at the beginning of the list of trees.
It is called a Fibonacci Heap because each tree of order k has at least Fk+2 nodes, where Fk+2 is the (k+2)th Fibonacci number.
In the following figure, you can see a Fibonacci Heap sample:
Figure 5.39: Fibonacci Heap sample
The main operations in a Fibonacci Heap are (Big O represents the amortized time): insert (O(1)), decrease key (O(1)), find the minimum (O(1)), extract minimum (O(log n)), deletion (O(log n)), and merge (O(1)). You can find an implementation of these operations in the bundled...
