ISRO-DEC2017-52

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

1. $10,8,7,5,3,2,1$
2. $10,8,7,2,3,1,5$
3. $10,8,7,1,2,3,5$
4. $10,8,7,3,2,1,5$

Comments

Resulting Max-heap after insertion of 1 & 7

Level-order traversal : 10 8 7 3 2 1 5

Option (d)

---

https://gateoverflow.in/1967/gate2014-2-12

Answer 1

                                                10 level 0

                                        8                        5 level1

                             3                 2                                level 2

after insertion of...

                                            

                                               10 level 0

                                        8                        5 level1

​​​​​​​                          3                     2            1                     level 2

heap property is still satisfied... then we will insert next 7

                                         

                                              10 level 0

                                        8                        5 level1

​​​​​​​                          3                     2            1                 7   level 2

here 5<7 then swap 7 & 5....

                                           

                                              10 level 0

                                        8                        7 level1

​​​​​​​                          3                     2            1                 5   level 2

  .....

now traverse...10,8,7,3,2,1,5