How to create a heap?

Question

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?

Option 1.

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

Option 2.

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

Option 3.

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

Which is the correct step? And Why? Please explain.

Answer 1

Option 1 is right.. Because 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 ... SO your option 1 is right.

here you can see heap sort example in detail.. This link states a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.) There is no restriction as to how many children each node has in a heap, although in practice each node has at most two.

Good Luck

Answer 2

Option 1, by definition binary heap's shape is a complete binary tree. The other 2 are not complete binary trees. See http://en.wikipedia.org/wiki/Binary_heap