Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8,…
2015
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
Attempted by 206 students.
Show answer & explanation
Correct answer: B
Solution: Insert 35 at the next available position and restore the max-heap by bubbling it up as needed.
Step 1: Insert 35 at index 10 (append to the array).
Array after insertion: 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
Step 2: Compare 35 with its parent at index 5 (value 15). Since 35 > 15, swap them.
Array after swap: 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
Step 3: Now 35 is at index 5. Compare it with its parent at index 2 (value 30). Since 35 > 30, swap them.
Array after swap: 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
Step 4: 35 is now at index 2. Its parent at index 1 is 40, and 35 < 40, so the heap property is satisfied and bubbling stops.
Final heap array: 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
A video solution is available for this question — log in and enroll to watch it.