# inserting into min heap

These are the instructions I been given :

What does the array look like at each step when inserting "2" into the following min-heap?

Give your answer as comma-separated numbers, with a space after each number, eg., 0, 2, 3, 4

The heap starts at entry 1 (second entry) of the array, so begin with "0,..." for the unused entry. and I need to write down the array at each step like

Immediately after item is added: for this step I got 4 6 8 7 2

After first sift up step: 4 2 8 7 6

but that is wrong apparently? I'm not sure why also I'm not sure where and why I'm suppose to put a 0.. is there a different way to write it?

For any element at index $$i$$ store its left chid at index $$2i +1$$ and right child at index $$2i+2$$.

Your heap in the form of array without any insertion. The $$0$$ in the array given below means no key at that index. $$\fbox{4}\fbox{6} \fbox{8} \fbox{7}\fbox{0}\fbox{0} \fbox{0} \fbox{0}$$

After inserting $$2$$.

$$\fbox{4}\fbox{6} \fbox{8} \fbox{7}\fbox{2}\fbox{0} \fbox{0} \fbox{0}$$

But you need to maintain the min heap property. So

$$\fbox{4}\fbox{2} \fbox{8} \fbox{7}\fbox{6}\fbox{0} \fbox{0} \fbox{0}$$

Again $$2$$ is less than $$8$$. So

$$\fbox{2}\fbox{4} \fbox{8} \fbox{7}\fbox{6}\fbox{0} \fbox{0} \fbox{0}$$

• but it says 'The heap starts at entry 1 (second entry) of the array, so begin with "0,..." for the unused entry'? – Danny Oct 5 at 19:29
• @Danny I have edited the answer. The heap entry starts at $1$ no problem. – aaag Oct 6 at 15:11

The contents of the heap look like this: 04687, 046872, 042876, 024876. I have prefixed a 0 because, as you mention, the heap contents actually start in the second position.