0
$\begingroup$

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.

enter image description here

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?

$\endgroup$
1
$\begingroup$

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}$$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.