Suppose we are sorting(increasing/ decreasing) an array of 10 unsorted elements. We have just finished some heapify(max heapify/ min heapify) operations. The array now looks like: 9, 8, 10, 7, 5, 6, 4, 3, 2, 1. How many heapify operations have been performed on the root so far ?
In Heapsort, we first build a heap, then we do following operations till the heap size becomes 1.
a) Swap the root with last element
b) Call heapify for root
c) reduce the heap size by 1.
In this question, it is given that heapify has been called few times and we see that last four elements in given array are the 4 minimum elements in array. So situation is clear, it is minheapify which has been called 4 times.
Answer : 4 heapify operations have been performed.