The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a maxHeap. The resultant maxHeap is A. (tree with 32 at root, 30 and 25 as children, 15 and 12 as left subtree leaves, 20 and 16 as right subtree leaves) B. (tree with 32 at root, 30 and 25 as children, 15 and 12 and 20 and 16 at lower level) C. (tree with 32 at root, 15 and 25 as children) D. (tree with 32 at root, 30 and 25 as children, 15 and 12 at left, 20 and 16 at right)

GATE 2004 · Programming and Data Structures · Binary Heap · easy

Answer: The resultant max-heap has array representation [32, 30, 25, 15, 12, 20, 16]: root=32, left subtree rooted at 30 (with children 15 and 12), right subtree rooted at 25 (with children 20 and 16). Answer: A.

1. Insert elements one by one with bubble-up: Insert 32: heap=[32]. Insert 15: heap=[32,15] (15 < 32, no swap). Insert 20: heap=[32,15,20] (20 < 32, no swap). Insert 30: heap=[32,15,20,30] -> 30>15, swap -> [32,30,20,15] -> 30<32, stop. Insert 12: heap=[32,30,20,15,12] (12<30, no swap). Insert 25: heap=[32,30,20,15,12,25] -> 25>20, swap -> [32,30,25,15,12,20] -> 25<32, stop. Insert 16: heap=[32,30,25,15,12,20,16] -> 16<25, no swap.
2. Verify final heap structure: Final array: index 1=32 (root), index 2=30 (left child of root), index 3=25 (right child of root), index 4=15 (left child of 30), index 5=12 (right child of 30), index 6=20 (left child of 25), index 7=16 (right child of 25). Check: 32>=30, 32>=25, 30>=15, 30>=12, 25>=20, 25>=16. All satisfied.