Heap Question

Question

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 ?

Comments

max heap and 4 max heapify operation

I think

---

right

please explain

---

Yes it should be 4 operation of max heap.

Construct the heap from this sequence, now apply heapify from bottom to top, there you will find that 5 is the parent of 1, next internal node is 7 which is the parent of 3 and 2, similarly for 10 and 8,

Since in the question it is given that, 

We have just finished some heapify(max heapify/ min heapify) operations.

Means we have still not done with heap, we need one more operation to completely convert it into max heap, which is swap 9 and 10,

Now, its completely converted into max heap. 

---

ok ,then how you decide it is 4

---

1st max heap on 5, second on 7, third on 10 and forth on 8.

hence it is 4

Now, if we do 5th on 9 then it will be completely a max heap.

---

thanks

---

It's 4 on a min-heap. Look at the details. It is sorting an array. And the state now is 9,8,10,7,5,6,4,3,2,1. 

Only in a min-heap the root element (least big) is extracted and put at the end of the array. 

Answer 1

As it is told in question We have just finished some heapify

So, there must we found some heap trees

We tried first with min heap operation. There no leaf satisfies minheap operations

So, now try with max heap

So, 4 max heap sub trees we found , though root 9 stillneed to heapify