4,130 views
6 votes
6 votes

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?

1 Answer

1 votes
1 votes
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 two elements in given array are the 2 maximum elements in array. So situation is clear, it is Max heapify which has been called 2 times.
edited by

Related questions

1 votes
1 votes
3 answers
1
Balaji Jegan asked Jun 17, 2018
3,358 views
How many element comparisons would heap sort use to sort the integers $1$ to $8$ if they wereinitially in sorted order, initially in reverse sorted order?
0 votes
0 votes
0 answers
2
1 votes
1 votes
0 answers
3
Prajwal Bhat asked Dec 20, 2016
591 views
Need approach to solve this ?
1 votes
1 votes
1 answer
4
Rajesh Pradhan asked Nov 21, 2016
1,355 views
There are 3 D&C basis sorting AlgosQuick sort :- T(k)+T(n-k)+ CnMerge sort :- 2T(n/2) +Cn Heap sort :- ___________I know how the complexity of heap sort is O(nlogn) but ...