In: Computer Science
Give O(n) sequence of Fibonacci-heap operations, which creates a Fibonacciheap which has more number of marked nodes than the number of nodes that are not marked.
In terms of Time Complexity, Fibonacci Heap beats both Binary and Binomial Heaps.
Below are amortized time complexities of Fibonacci Heap.
1) Find Min: Θ(1) [Same as both Binary and Binomial] 2) Delete Min: O(Log n) [Θ(Log n) in both Binary and Binomial] 3) Insert: Θ(1) [Θ(Log n) in Binary and Θ(1) in Binomial] 4) Decrease-Key: Θ(1) [Θ(Log n) in both Binary and Binomial] 5) Merge: Θ(1) [Θ(m Log n) or Θ(m+n) in Binary and Θ(Log n) in Binomial]
Like Binomial Heap, Fibonacci Heap is a collection of trees with min-heap or max-heap property. In Fibonacci Heap, trees can 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
Fibonacci Heap maintains a pointer to minimum value (which is root of a tree). All tree roots are connected using circular doubly linked list, so all of them can be accessed using single ‘min’ pointer.
The main idea is to execute operations in “lazy” way. For example merge operation simply links two heaps, insert operation simply adds a new tree with single node. The operation extract minimum is the most complicated operation. It does delayed work of consolidating trees. This makes delete also complicated as delete first decreases key to minus infinite, then calls extract minimum.
Some facts about Fibonacci Heap