The Gateway to Computer Science Excellence
+21 votes
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 by Boss (30.8k points)
edited by | 1.6k views

2 Answers

+38 votes
Best answer
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 by
0
heap is complete binary tree or almost complete binary tree ?
+2
Heap is almost complete binary tree, need not to be complete.
+3 votes
answer is b
by Active (1.4k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,355 answers
198,481 comments
105,249 users