Answer (C)
Heapify works this way:
- At each iteration, we apply heapify on a specific segment of an array
- We start by applying heapify on entire array (of length $N$), so we get (max / min) element as the root (i.e. index $0$) of array.
- We pick this root element (index $0$) and replace it with last element of array (index $N-1$)
- Now, we apply heapify on the remaining $N-1$ length of array beginning from root index ($0$) to last second last index ($N-2$)
- We again pick the root element (index $0$) and replace it with second last element of array (index $N-2$)
- And so on.. until no segment is left
So, it is clear that after each iteration, we get max (or min) element at the last array index (after replace)
Array in question looks like this
16 14 15 10 12 27 28
It can be seen that last two elements are maximum elements of array and the we have just finished heapify, so root (index $0$) is having maximum element in that segment (index $0$ to $N-3$) on which heapify was applied.
So heapify must have been applied 3 times.