GATE CSE 2015 Set 1 | Question: 32

Question

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

• A. $40, 30, 20, 10, 15, 16, 17, 8, 4, 35$
• B. $40, 35, 20, 10, 30, 16, 17, 8, 4, 15$
• C. $40, 30, 20, 10, 35, 16, 17, 8, 4, 15$
• D. $40, 35, 20, 10, 15, 16, 17, 8, 4, 30$

Answer 1

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$

Comments

heap is complete binary tree or almost complete binary tree ?

---

Heap is almost complete binary tree, need not to be complete.

---

every almost complete binary tree is also  complete binary tree .

---

Arjun sir never provide easy question solution but why here :p