0 votes 0 votes 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? Algorithms binary-heap + – pradeepchaudhary asked Jul 8, 2018 pradeepchaudhary 2.0k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Shaik Masthan commented Jul 8, 2018 reply Follow Share 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 0 votes 0 votes MiNiPanda commented Jul 8, 2018 reply Follow Share 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? 0 votes 0 votes Shaik Masthan commented Jul 8, 2018 reply Follow Share @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. 0 votes 0 votes MiNiPanda commented Jul 8, 2018 reply Follow Share 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. 0 votes 0 votes Shaik Masthan commented Jul 8, 2018 reply Follow Share 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 0 votes 0 votes MiNiPanda commented Jul 8, 2018 reply Follow Share 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? 0 votes 0 votes Shaik Masthan commented Jul 8, 2018 reply Follow Share 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? 0 votes 0 votes MiNiPanda commented Jul 8, 2018 reply Follow Share Did you upload any image? Because you said "it turned out like this.." after that blank space :( 0 votes 0 votes Please log in or register to add a comment.