GATE CS 2014 Set 2 Q12 — Binary Heaps

To find the level-order traversal after inserting the elements, we can trace the operations step-by-step on the Max-Heap.

Step 1: Initial Max-Heap

The initial level-order traversal is $10, 8, 5, 3, 2$. Represented as a complete binary tree:

      10
     /  \
    8    5
   / \
  3   2

Step 2: Insert $1$

We insert $1$ at the next available position (the left child of $5$):

      10
     /  \
    8    5
   / \  /
  3   2 1

Since the parent node $5 \ge 1$, the max-heap property is satisfied. No swaps are needed.

Step 3: Insert $7$

We insert $7$ at the next available position (the right child of $5$):

      10
     /  \
    8    5
   / \  / \
  3   2 1  7

Since the parent node $5 < 7$, we swap $7$ with $5$ (heapify-up):

      10
     /  \
    8    7
   / \  / \
  3   2 1  5

Now, we compare $7$ with its new parent $10$. Since $10 \ge 7$, the heapify-up process terminates.

Conclusion

The final level-order traversal of the heap is obtained by reading the nodes level-by-level from left to right:

$$\mathbf{10, 8, 7, 3, 2, 1, 5}$$

This matches Option A.