Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on {25, 14, 16, 13, 10, 8, 12}? A. {14, 13, 12, 10, 8} B. {14, 12, 13, 10, 8} C. {14, 13, 8, 10, 12} D. {14, 13, 12, 8, 10}
GATE 2009 · Programming and Data Structures · Binary Heap · medium
Answer: The array after two delete operations is {14, 13, 12, 8, 10} — option D.
- First delete-max: remove 25: Initial: [25, 14, 16, 13, 10, 8, 12]. Remove 25, move last element 12 to root → [12, 14, 16, 13, 10, 8]. Sift down 12: children are 14 (index 2) and 16 (index 3); largest child = 16. Swap 12 and 16 → [16, 14, 12, 13, 10, 8]. Now 12 is at index 3 (0-indexed: index 2), its children in 1-indexed array are at positions 5 and 6 which are 8 and nothing relevant — actually node at position 3 (1-indexed) has children at 6 and 7: values 8 and (out of bounds after removal). 8 < 12, no swap needed. Result: [16, 14, 12, 13, 10, 8].
- Second delete-max: remove 16: Current heap: [16, 14, 12, 13, 10, 8]. Remove 16, move last element 8 to root → [8, 14, 12, 13, 10]. Sift down 8: children are 14 (pos 2) and 12 (pos 3); largest = 14. Swap 8 and 14 → [14, 8, 12, 13, 10]. Now 8 is at position 2; its children are 13 (pos 4) and 10 (pos 5). Largest child = 13 > 8, swap → [14, 13, 12, 8, 10]. Node 8 is now at position 4; its children would be at positions 8 and 9, which are out of bounds. Sift-down complete. Result: [14, 13, 12, 8, 10].