Project ForgeData Structures
Trees
GATE 2009
Hard
What is the content of the array {25, 14, 16, 13, 10, 8, 12} after two delete (extract-max) operations on this binary max-heap?
- A{14, 13, 12, 10, 8}
- B{14, 12, 13, 8, 10}
- C{14, 13, 8, 12, 10}
- {14, 13, 12, 8, 10}
Explanation
First delete-max: remove 25, move last(12) to root: {12,14,16,13,10,8}, sift down — swap with larger child 16: {16,14,12,13,10,8}, 12's children(only index5=8) fine, no further swap. Second delete-max: remove 16, move last(8) to root: {8,14,12,13,10}, sift down — swap with larger child 14: {14,8,12,13,10}, then 8's children(13,10) — swap with larger(13): {14,13,12,8,10}. Final: {14,13,12,8,10}.
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.