Insert item into the Heap. Explain your actions.

Suppose I have a Heap Like the following:

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55

Now, I want to insert another item 55 into this Heap. How to do this?

A binary heap is defined as a binary tree with two additional constraints:

• Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node’s children, according to some total order.

We start adding child from the most left node and if the parent is lower than the newly added child than we replace them. And like so will go on until the child got the parent having value greater than it.

Your initial tree is:

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55

Now adding 55 according to the rule on most left side:

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55
/
55

But you see 22 is lower than 55 so replaced it:

       77
      /  \
     /    \
    50    60
   / \    / \
  55 30  44 55
 /
22 

Now 55 has become the child of 50 which is still lower than 55 so replace them too:

       77
      /  \
     /    \
    55    60
   / \    / \
  50 30  44 55
 /
22

Now it cant be sorted more because 77 is greater than 55.