Insertion Operation in Max Heap

Finding Maximum Value Operation in Max Heap

It's easy to find the node in a max heap with the highest value. The root node in the max heap has the highest value of all the other nodes in the max heap. As a result, we can display the value of the root node as the maximum value in the max heap.

Insertion Operation in Max Heap

Insertion Operation in max heap is performed as follows...

• Step 1: Insert the newNode as last leaf from left to right.
• Step 2: Compare newNode value with its Parent node.
• Step 3: If newNode value is greater than its parent, then swap both of them.
• Step 4: Repeat step 2 and step 3 until newNode value is less than its parent nede (or) newNode reached to root.

Example
Consider the above max heap. Insert a new node with value 85.

• Step 1: Insert the newNode with value 85 as last leaf from left to right. That means newNode is added as a right child of node with value 75. After adding max heap is as follows.
• 
• Step 2: Compare newNode value (85) with its Parent node value (75). That means 85 > 75
• 
• Step 3: Here newNode value (85) is greater than its parent value (75), then swap both of them. After swapping, the max heap is as follows...
• 
  
• 
• Step 4: Now, again compare the newNode value (85) with its parent node value (89).
• 
• Here, the newNode value (85) is smaller than its parent node value (89). So, we stop the insertion process. Finally, the max heap after insertion of a new node with value 85 is as follows...
•