edited by
6,930 views
28 votes
28 votes

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$
edited by

1 Answer

Best answer
44 votes
44 votes
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$
edited by
Answer:

Related questions

23 votes
23 votes
4 answers
1
25 votes
25 votes
3 answers
3
65 votes
65 votes
12 answers
4