Inserting elements into Binary Min Heaps

Question

If I am inserting items: 10,12,14,1,6 into a binary min heap one item after another how would the results look like, my problem is with the following

when i start i have:

10

then

   10
  /
 12

then

   10
  /  \
 12  14

then

   1
  / \
 10 14
 /
12

but this is not right, so what is the right way to do that?

Note: this is a homework question, i am trying to understand the concept, if you don't feel comfortable solving the question (it is not the full question anyway) please provide an example with similar issue.

Answer 1

You have to add the new element as a child (or leaf exactly) to the heap (not as root), that means you put it in the first "right" free spot (or in your heap-array, just at the end).

Then you have to re-establish the heap conditions, this is called "heapify". This happens in two phases:

1. Repeatedly exchange the new element (general: the element that violates the heap conditions) with its parent node as long as it is smaller than the parent and it is not the root.
2. Repeatedly exchange the new element with the child with the smallest value, until the new element becomes a leave or both child nodes are bigger than the element itself.

That means

   10
  /  \
12    14

+ 1 leads to

    10
   /  \
 12    14
 /
1

And that violates the heap conditions, so you have to heapify

    10
   /  \
  1   14
 /
12

But this is still not right, so you have to heapify again

     1
   /  \
 10   14
 /
12

And there you are... everything OK now :-)