A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements.…
2005
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
- A.
10, 8, 7, 5, 3, 2, 1
- B.
10, 8, 7, 2, 3, 1, 5
- C.
10, 8, 7, 1, 2, 3, 5
- D.
10, 8, 7, 3, 2, 1, 5
Attempted by 228 students.
Show answer & explanation
Correct answer: D
Solution: Show insertion steps and final level-order traversal.
Initial heap (level-order): 10, 8, 5, 3, 2
Insert 1: append as the last element. Array becomes 10, 8, 5, 3, 2, 1. 1's parent is 5 which is larger, so no percolate-up occurs.
Insert 7: append to get 10, 8, 5, 3, 2, 1, 7. 7's parent is 5, and since 7 > 5, percolate-up swaps them.
After swapping 7 with 5: 10, 8, 7, 3, 2, 1, 5
Now 7's parent is 10 which is larger, so percolation stops.
Final heap (level-order): 10, 8, 7, 3, 2, 1, 5
Key idea: insertions append at the end; then percolate-up swaps with parent if the new element is larger, preserving the max-heap property.