Fibonacci Heap

 Fibonacci Heap 

Fibonacci heap is a modified form of a binomial heap with more efficient heap  operations than that supported by the binomial and binary heaps. 

Unlike binary heap, a node can have more than two children. 

The fibonacci heap is called a fibonacci heap because the trees are  constructed in a way such that a tree of order n has at least Fn+2 nodes in it,  

where Fn+2 is the (n + 2)nd Fibonacci number. 

Fibonacci  Heap 

Properties of a Fibonacci Heap 

Important properties of a Fibonacci heap are: 

1. It is a set of min heap-ordered trees. (i.e. The parent is always smaller than  the children.)

2. A pointer is maintained at the minimum element node. 

3. It consists of a set of marked nodes. (Decrease key operation) 4. The trees within a Fibonacci heap are unordered but rooted. 

Memory Representation of the Nodes in a Fibonacci  Heap 

The roots of all the trees are linked together for faster access. The child nodes  of a parent node are connected to each other through a circular doubly linked  list as shown below. 

There are two main advantages of using a circular doubly linked list. 

1. Deleting a node from the tree takes O(1) time. 

2. The concatenation of two such lists takes O(1) time. 

Operations on a Fibonacci Heap

Insertion 

Algorithm 

insert(H, x)   degree[x] = 0   p[x] = NIL   child[x] = NIL   left[x] = x   right[x] = x   mark[x] = FALSE   concatenate the root list containing x with root list H    if min[H] == NIL or key[x] < key[min[H]]   then min[H] = x   n[H] = n[H] + 1

Inserting a node into an already existing heap follows the steps below. 1. Create a new node for the element. 

2. Check if the heap is empty. 

3. If the heap is empty, set the new node as a root node and mark it . 

min

4. Else, insert the node into the root list and update .

min

Insertion Example 

Find Min 

The minimum element is always given by the pointer. 

min

Union 

Union of two fibonacci heaps consists of following steps. 

1. Concatenate the roots of both the heaps.

2. Update by selecting a minimum key from the new root lists. 

min

Union of two heaps 

Extract Min 

It is the most important operation on a fibonacci heap. In this operation, the node with  minimum value is removed from the heap and the tree is re-adjusted. 

The following steps are followed: 

1. Delete the min node. 

2. Set the min-pointer to the next root in the root list. 

3. Create an array of size equal to the maximum degree of the trees in the heap before  deletion. 

4. Do the following (steps 5-7) until there are no multiple roots with the same degree. 5. Map the degree of current root (min-pointer) to the degree in the array. 6. Map the degree of next root to the degree in array.

7. If there are more than two mappings for the same degree, then apply union  operation to those roots such that the min-heap property is maintained (i.e. the  minimum is at the root). 

An implementation of the above steps can be understood in the example below. 

1. We will perform an extract-min operation on the heap below. 

Fibonacci Heap 

Delete the min node, add all its child nodes to the root list and set the min pointer to the next root in the root list.

Delete the min node 

The maximum degree in the tree is 3. Create an array of size 4 and map  degree of the next roots with the array. 

Create an array 

Here, 23 and 7 have the same degrees, so unite them 

Again, 7 and 17 have the same degrees, so unite them as well.

Unite those having the same degrees 

Again 7 and 24 have the same degree, so unite them.

Unite those having the same degrees 

Map the next nodes

Map the remaining nodes 

Again, 52 and 21 have the same degree, so unite them

Unite those having the same degrees 

Similarly, unite 21 and 18.

Map the remaining root

Map the remaining nodes 

The final heap is.

Final fibonacci heap 

. 

Fibonacci Heap – Deletion, Extract min and  Decrease key 

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: 1. Delete the min node. 

2. Set head to the next min node and add all the tree of the  deleted node in root list. 

3. Create an array of degree pointers of the size of the deleted  node. 

4. Set degree pointer to current node. 

5. 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. 

6. Repeat steps 4 and 5 until the heap is completed. 

Example: 

0

1

2

7 4 3 96

7 AND 4 Same Degree 

 Min 

3 4 

7 6 

9

Decrease_key(): To decrease the value of any element in the  heap, we follow the following algorithm: 

• Decrease the value of the node ‘x’ to the new chosen value. • CASE 1) If min heap property is not violated, 

• Update min pointer if necessary. 

• CASE 2) If min heap property is violated and parent of ‘x’ is   unmarked, 

• Cut off the link between ‘x’ and its parent. 

• Mark the parent of ‘x’. 

• Add tree rooted at ‘x’ to the root list and update min pointer if  necessary. 

• CASE 3)If min heap property is violated and parent of ‘x’ is marked, • Cut off the link between ‘x’ and its parent p[x]. 

• Add ‘x’ to the root list, updating min pointer if necessary. • Cut off link between p[x] and p[p[x]]. 

• Add p[x] to the root list, updating min pointer if necessary. 

• If p[p[x]] is unmarked, mark it. 

• Else, cut off p[p[x]] and repeat steps 4.2 to 4.5, taking p[p[x]] as ‘x’. Example: 

Deletion(): To delete any element in a Fibonacci heap, the  following algorithm is followed: 

1. Decrease the value of the node to be deleted ‘x’ to minimum  by Decrease_key() function. 

2. By using min heap property, heapify the heap containing ‘x’,  bringing ‘x’ to the root list. 

3. Apply Extract_min() algorithm to the Fibonacci heap. Example: