Explain the Delete Node operation on a Fibonacci Heap. | Data Structure Tutorial

In this article, you will understand what is the Decrease key and Delete node operations on a Fibonacci Heap.

A Fibonacci heap is a data structure that comprises a collection of trees that will follow the property of a min heap or max heap. The min heap and max heap are the characteristics of the trees present on a Fibonacci heap. In a Fibonacci heap, a node can have either more than two heap operations or no children at all. 

The two operations are:

• Decrease a Key: down the value of the key to any lower limit value.
• Delete a node: It deletes the given node.

Decreasing a key

In a decreasing key operation, the value of the key is decreased to the lower limit of the value.

The steps used in decreasing the key are:

• Choose the node whose values are to be decreased, i , and change its value to the new value j.
• If the parent of i, k, is not null and the key of a parent is greater than that of the new value i.e j then call cut(i) and cascading-cut(k) functions subsequently. 
• If the key of i is smaller than the key of min, then mark i as min.

Cut

1. Remove i from the current position and add it to the root list.
2. If i is marked, then mark it as false.

Cascading-Cut

1. if the parent of k is not null the approach towards the following steps.
2. if k is unmarked, then mark k.
3. Else, call cut(k) and cascading-cut(parent of k)

Deleting a Node

This process makes use of decrease-key and extract-min operations. The following steps are followed to delete the node:

1. Let k be the node that is deleted.
2. Apply decrease-key operation to decrease the value of the k to the lowest possible value.
3. Apply extract-min operation to delete the node.