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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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?

0

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

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

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

@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.

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

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

0

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

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

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

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?

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 584
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,121 questions

53,242 answers

184,708 comments

70,481 users