Insert items into binary mini-heaps

Question

If I insert elements: 10,12,14,1,6 into the binary mini-heap of one element after another, what would the results look like, my problem is related to the following

when i start:

10 

then

  10 / 12 

then

  10 / \ 12 14 

then

  1 / \ 10 14 / 12 

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

Note: this is a homework question, I'm trying to understand the concept, if you do not feel comfortable solving the question (this is not a complete question), please provide an example with a similar problem.

Answer 1

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

Then you need to restore the heap conditions, this is called "heapify". This occurs in two phases:

• Repeatedly exchange a new element (general: an element that violates the heap conditions) with its parent node, if it is less than the parent and is not root.
• Repeatedly exchange a new element with a child with the smallest value, until the new element becomes a departure, or both child nodes are larger than the element itself.

It 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 the case, so you need to inherit again

  1 / \ 10 14 / 12 

And here you are ... everything is fine now :-)

Answer 2

 step1: 10 step2: 10 / 12 step3: 10 / \ 12 14 step4: 1 / \ 10 12 / 14 step5: 1 / \ 6 10 / \ 12 14