Fibonacci Heap Creation and Insertion

#techlearners
Fibonacci heaps are linked lists of heap ordered
Trees with following characteristics –
Trees are not necessarily binomial.
Siblings are Bi-directionally linked.
There is a pointer min{H] to the root with minimum key.
The root degrees are not unique.
Special attributes n[H] maintains total number of nodes.
Nodes may be marked

Fibonacci Heap Creation
To create an empty Fibonacci heap MAKE_FIB_HEAP procedure allocates and returns Fibonacci heap object H, where n[H]=0 and min[H]=Nil.

The amortized cost of MAKE_FIB_HEAP is O(1)

Fibonacci Heap Insertion
Create a new singleton tree.
Add to left of min pointer.
Update min pointer.

Running time. O(1) amortized
Actual cost = O(1).
Change in potential = +1.
Amortized cost = O(1).



TECHLEARNERS BY NEERAJ SAXENA
http://www.techlearners.co.in