geeksforgeeks

Question

Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this:
16 14 15 10 12 27 28
How many heapify operations have been performed on root of heap?
(A) 1
(B) 2
(C) 3 or 4
(D) 5 or 6


Answer: (B)
 

Answer 1

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.

Comments

Got it! :)

---

what is the final tree after performing all operation??

---

Since we have only 2 max elements in ascending order at the end of array. The Maxheapify function was applied twice.