1.6k views

Consider a max heap, represented by the array: $40, 30, 20, 10, 15, 16, 17, 8, 4$.

$$\begin{array}{|l|l|}\hline \text{Array index} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} & \text{6} & \text{7} & \text{8} & \text{9} \\\hline \text{Value} & \text{40} & \text{30} & \text{20} & \text{10} &\text{15} & \text{16} & \text{17} & \text{8} & \text{4} \\\hline \end{array}$$

Now consider that a value $35$ is inserted into this heap. After insertion, the new heap is

1. $40, 30, 20, 10, 15, 16, 17, 8, 4, 35$
2. $40, 35, 20, 10, 30, 16, 17, 8, 4, 15$
3. $40, 30, 20, 10, 35, 16, 17, 8, 4, 15$
4. $40, 35, 20, 10, 15, 16, 17, 8, 4, 30$
in DS
edited | 1.6k views

Heap is complete binary tree. To insert a new element, we put it at the end of the tree and move up towards root till heap property is satisfied. Here, $35$ comes as child of $15$, with the path $40-30-15-35$. So, we swap $15, 35$ and then $30, 35$ to get the new path $40-35-30-15$. So, new heap will be $40 \ 35 \ 20 \ 10 \ 30 \ 16 \ 17 \ 8 \ 4 \ 15$.

Correct Answer: $B$
by Veteran (431k points)
edited
0
heap is complete binary tree or almost complete binary tree ?
+2
Heap is almost complete binary tree, need not to be complete.
by Active (1.4k points)