Deletion Operation in Max Heap

Data Structure using C 11:36 0

Deletion Operation in Max Heap

In a max heap, deleting last node is very simple as it is not disturbing max heap properties.

Deleting root node from a max heap is title difficult as it disturbing the max heap properties. We use the following steps to delete root node from a max heap...

Step 1: Swap the root node with last node in max heap
Step 2: Delete last node.
Step 3: Now, compare root value with its left child value.
Step 4: If root value is smaller than its left child, then compare left child with its right sibling. Else goto Step 6
Step 5: If left child value is larger than its right sibling, then swap root with left child. otherwise swap root with its right child.
Step 6: If root value is larger than its left child, then compare root value with its right child value.
Step 7: If root value is smaller than its right child, then swap root with rith child. otherwise stop the process.
Step 8: Repeat the same until root node is fixed at its exact position.

Example
Consider the above max heap. Delete root node (90) from the max heap.

Step 1: Swap the root node (90) with last node 75 in max heap After swapping max heap is as follows...
Step 2: Delete last node. Here node with value 90. After deleting node with value 90 from heap, max heap is as follows...
Step 3: Compare root node (75) with its left child (89).
Here, root value (75) is smaller than its left child value (89). So, compare left child (89) with its right sibling (70).
Step 4: Here, left child value (89) is larger than its right sibling (70), So, swap root (75) with left child (89).
Step 5: Now, again compare 75 with its left child (36).
Here, node with value 75 is larger than its left child. So, we compare node with value 75 is compared with its right child 85.
Step 6: Here, node with value 75 is smaller than its right child (85). So, we swap both of them. After swapping max heap is as follows...
Step 7: Now, compare node with value 75 with its left child (15).
Here, node with value 75 is larger than its left child (15) and it does not have right child. So we stop the process.

Finally, max heap after deleting root node (90) is as follows...