GATE CS 2004 Q37 — Binary Heaps

To find the correct max-heap, we insert the elements one by one into an initially empty binary max-heap. In a max-heap, the value of each node must be greater than or equal to the values of its children.

Step-by-step Insertion:

1. Insert 32:

       32
       

2. Insert 15:

         32
        /
       15
       

3. Insert 20:

         32
        /  \
       15  20
       

4. Insert 30:

   Initially placed as the left child of 15:

           32
          /  \
         15  20
        /
       30
       

   Since $30 > 15$, we swap them to restore the max-heap property:

           32
          /  \
         30  20
        /
       15
       

5. Insert 12:

   Placed as the right child of 30:

           32
          /  \
         30  20
        /  \
       15  12
       

6. Insert 25:

   Initially placed as the left child of 20:

            32
          /    \
         30    20
        /  \   /
       15  12 25
       

   Since $25 > 20$, we swap them:

            32
          /    \
         30    25
        /  \   /
       15  12 20
       

7. Insert 16:

   Placed as the right child of 25:

            32
          /    \
         30    25
        /  \   / \
       15  12 20 16
       

The array representation of the final max-heap is [32, 30, 25, 15, 12, 20, 16], which corresponds to the tree structure shown in Option A.