Design and Analysis of Algorithm

Fibonacci Heap – Deletion, Extract min and Decrease key In the last post, we discussed  Insertion and Union of Fibonacci Heaps.  In this post, we will discuss Extract_min(), Decrease_key() and Deletion() operations on Fibonacci heap. Prerequisites: Fibonacci Heap (Introduction) Fibonacci Heap – Insertion and Union Extract_min():  We create a function for deleting the minimum node and setting the min pointer to the minimum value in the remaining heap. The following algorithm is followed: Delete the min node. Set head to the next min node and add all the tree of the deleted node in root list. Create an array of degree pointers of the size of the deleted node. Set degree pointer to current node. Move to the next node. If degrees are different then set degree pointer to next node. If degrees are same then join the Fibonacci trees by union operation. Repeat steps 4 and 5 until the heap is completed. Example: Decrease_key():  To decrease the value of any element in

Fibonacci Heap – Insertion and Union 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). In this article, we will discuss Insertion and Union operation on Fibonacci Heap. Insertion:  To insert a node in a Fibonacci heap H, the following algorithm is followed: Create a new node ‘x’. Check whether heap H is empty or not. If H is empty then: Make x as the only node in the root list. Set H(min) pointer to x. Else: Insert x into root list and update H(min). Example: Union:  Union of two Fibonacci heaps H1 and H2 can be accomplished as follows: Join root lists of Fibonacci heaps H1 and H2 and make a single Fibonacci heap H. If H1(min) < H2(min) then: H(min) = H1(min). Else: H(min) = H2(min). Example:

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 taken from  here . 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 operati