NIELIT 2017 July Scientist B (CS) - Section B: 8

Question

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$

Comments

Same questiion asked from GATE CS 2014 : https://gateoverflow.in/1967/gate2014-2-12

Answer 1

After inserting 1: 10, 8, 5, 3, 2, 1

After inserting 7: 10, 8, 7, 3, 2, 1, 5

Hence, option A.

Answer 2

Its MAX heap. Before insertion, BFS was 10,8,5,3,2. On insertion maintain the property of complete tree plus max heap. Thus the bfs traversal will be 10,8,7,3,2,1,5. Hence option A is correct