Decrease Key and Delete Node Operation on a Fibonacci Heap Data Structure | Data Structure Tutorial

Decrease Key and Delete Node Operation on a Fibonacci Heap Data Structure.

In this article, you will understand the Fibonacci operations of the Decrease key and delete the node.

It is a data structure that consists of a collection of trees that have a property of min heap or max heap property. These two properties are fundamental characteristics of the trees present on a Fibonacci heap. In the Fibonacci heap, the node can consist of more than two children and no children at all. It has more efficient heap operations than that supported by the binomial and binary heaps. It is known as a Fibonacci heap because the trees are constructed in a way such that a tree of order n has at least F(n+2) nodes in it.

Operations of Fibonacci Heap

• Decrease a key: It means we can decrease the value of a key to any lower value. 
• Delete a node: It deletes the given node. 

Decreasing a key

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

Functions used for decreasing the key:

• Decrease-Key

• Choose the node whose value is to be decreased, y, and change its value to the new value x.
• If the value of the parent of y, i is not null and the key of the parent must be larger than that of the x then call Cut(y) and Cascading-Cut(i).
• If the key of y is lesser than the key of min, then mark y as min.

• Cut

• Delete y from the present position and add it to the current root list. 
• If y is marked, then mark it as false. 

• Cascading-Cut

• If the parent of i is not null then follow the next steps.
• If i is unmarked, then mark i.
• Otherwise, call Cut(i) and Cascading-Cut(parent of i).

Deleting a Node

It uses the decrease-key and extract-min operations. The steps involved in this are:

• Let y be the node to be deleted.
• Apply decrease-key operation to decrease the value of y to the lowest possible value.
• Apply extract-min operation to delete this node.

Complexity

The decreased key case complexity is O(1).

The Delete node case complexity is O(log n).