GATE CS 2009 Q60 — Binary Heaps

A binary max-heap deletion is performed by replacing the root element with the last element of the heap, reducing the heap size by 1, and then performing a max-heapify operation from the root downwards.

Initial Max-Heap:
$\text{Array} = \{25, 14, 16, 13, 10, 8, 12\}$

First Delete Operation:

1. Remove the root element $25$ and replace it with the last element $12$.
   $\text{Array} \rightarrow \{12, 14, 16, 13, 10, 8\}$
2. Heapify down from the root ($12$):
   • Compare $12$ with its children $14$ and $16$. Since $16$ is the larger child, swap $12$ with $16$.
   • $\text{Array} \rightarrow \{16, 14, 12, 13, 10, 8\}$
   • Now, $12$ is at index 2. Its only child is $8$. Since $12 > 8$, the heap property holds.

Second Delete Operation:

1. Remove the root element $16$ and replace it with the last element $8$.
   $\text{Array} \rightarrow \{8, 14, 12, 13, 10\}$
2. Heapify down from the root ($8$):
   • Compare $8$ with its children $14$ and $12$. Since $14$ is the larger child, swap $8$ with $14$.
   • $\text{Array} \rightarrow \{14, 8, 12, 13, 10\}$
   • Now, $8$ is at index 1. Its children are $13$ and $10$. Since $13$ is the larger child, swap $8$ with $13$.
   • $\text{Array} \rightarrow \{14, 13, 12, 8, 10\}$

Thus, the final content of the array is $\{14, 13, 12, 8, 10\}$.