Heap Sort :

Question

Q) 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?

Comments

i'm not getting how 10,12 and 27,28 are at last level by doing the heapifying?

if it is max heap, how 15 or 16 is above of 27 and 28

if it is min heap, how 14 or 16 is above of 10 and12

---

Is it 2?

Shaik Masthan the question says that "some" heapify function has been performed..not all. Then can't we say that since 27 and 28 are in their correct positions so the heap has been heapified twice?

---

@MiniPanda, yes i agree that but my doubt is at a time 27 and 28 both can be change?

at process of heapifying, i get only one element is changing...

 

give your explanation for 2... atleast then also i may understand.

---

The initial array given was suppose 16,14,28,10,12,27,15. We create a max heap now. Then it becomes 28,14,27,10,12,16,15.

Now apply extract_Max --> we swap 28(root node) with the last leaf node(15).

Array becomes -> 15,14,27,10,12,16,28.

So 28 gets the last index and apply Maxheapify on 15(now the root node).

Now the array becomes 27,14,15,10,12,16.

Again apply extract_Max --> we swap 27(root node) with the last leaf node(16).

Now array looks like 16,14,15,10,12,27,28.

Okay..i think only one Maxheapify function is enough.

---

you did a mistake, " Now the array becomes 27,14,15,10,12,16. "

array becomes  27,14,16,10,12,15 ====> it will give 2 Max heapify's...

 

but my doubt is for considering array , you are using all elements...

but while doing heapify, you are not considering all elements (why because you extract them ),

this is true when he gave array contain non-sorted + sorted elements...

 

if that is default, then any one can say easily that how many heapify operations performed by observing how many sorted elements are consecutive... here 27 and 28 are consecutive ==> 2 Max heapifies

---

Yes you are right..the array becomes  27,14,16,10,12,15 .

After swapping 15,14,16,10,12. Then  Maxheapify on 15 to get 16,14,15,10,12.

if that is default, then any one can say easily that how many heapify operations performed by observing how many sorted elements are consecutive... here 27 and 28 are consecutive ==> 2 Max heapifies

Yes..right..i don't know whether this is the correct answer but what else should be..and why?

I also could not understand your doubt..can you please elaborate?

---

actually there are 8 elements... after extracting one element, it turned out like this....

 

if it is only 7 elements... and non-sorted and sorted elements, he should mention, upto where it is sorted?

---

Did you upload any image?  Because you said "it turned out like this.." after that blank space :(