Consider a max heap, represented by the array: 23, 17, 14, 6, 13, 10, 1, 5 If…
2021
Consider a max heap, represented by the array: 23, 17, 14, 6, 13, 10, 1, 5 If a value 20 is inserted into this heap, then what will be the new max heap?
- A.
23, 17, 4, 6, 13, 10, 1, 5, 20
- B.
23, 20, 14, 17, 13, 10, 1, 5, 6
- C.
23, 20, 17, 14, 13, 10, 6, 5, 1
- D.
23, 17, 20, 14, 13, 10, 6, 5, 1
Attempted by 196 students.
Show answer & explanation
Correct answer: B
To insert 20 into the max heap represented by the array [23, 17, 14, 6, 13, 10, 1, 5], follow these steps:
Step 1: Add 20 at the end of the array: [23, 17, 14, 6, 13, 10, 1, 5, 20].
Step 2: Perform the heapify-up (or bubble-up) process. Compare 20 with its parent (5 at index 4). Since 20 > 5, swap them. The array becomes [23, 17, 14, 6, 13, 10, 1, 20, 5].
Step 3: Now 20 is at index 8. Its parent is 13 at index 3. Since 20 > 13, swap them. The array becomes [23, 17, 14, 20, 13, 10, 1, 6, 5].
Step 4: Now 20 is at index 3. Its parent is 17 at index 1. Since 20 > 17, swap them. The array becomes [23, 20, 14, 17, 13, 10, 1, 6, 5].
Step 5: Now 20 is at index 1. Its parent is 23 at index 0. Since 20 < 23, the heap property is satisfied. No further swaps are needed.
Final max heap: [23, 20, 14, 17, 13, 10, 1, 6, 5].