A priority queue is implemented as a Max-Heap. Initially, it has 5 elements.…
2014
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
- A.
10, 8, 7, 3, 2, 1, 5
- B.
10, 8, 7, 2, 3, 1, 5
- C.
10, 8, 7, 1, 2, 3, 5
- D.
10, 8, 7, 5, 3, 2, 1
Attempted by 236 students.
Show answer & explanation
Correct answer: A
Final heap (level-order): 10, 8, 7, 3, 2, 1, 5
Start with the initial heap: [10, 8, 5, 3, 2].
Insert 1 at the next leaf position → [10, 8, 5, 3, 2, 1]. 1 < parent 5, so no swap; heap property holds.
Insert 7 at the next leaf position → [10, 8, 5, 3, 2, 1, 7]. Compare with parent 5: 7 > 5, so swap them → [10, 8, 7, 3, 2, 1, 5].
Now 7's parent is 10 and 7 < 10, so no further swaps. The max-heap property holds and the level-order traversal is 10, 8, 7, 3, 2, 1, 5.
A video solution is available for this question — log in and enroll to watch it.