retagged by
8,834 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?
(A) 1
(B) 2
(C) 3 or 4
(D) 5 or 6


Answer: (B)
 

retagged by

1 Answer

Best answer
2 votes
2 votes

Answer (C)

Heapify works this way:

  • At each iteration, we apply heapify on a specific segment of an array
  • We start by applying heapify on entire array (of length $N$), so we get (max / min) element as the root (i.e. index $0$) of array.
  • We pick this root element (index $0$) and replace it with last element of array (index $N-1$)
  • Now, we apply heapify on the remaining $N-1$ length of array beginning from root index ($0$) to last second last index ($N-2$)
  • We again pick the root element (index $0$) and replace it with second last element of array (index $N-2$)
  • And so on.. until no segment is left

So, it is clear that after each iteration, we get max (or min) element at the last array index (after replace)

Array in question looks like this

16 14 15 10 12 27 28

It can be seen that last two elements are maximum elements of array and the we have just finished heapify, so root (index $0$) is having maximum element in that segment (index $0$ to $N-3$) on which heapify was applied.

So heapify must have been applied 3 times.

selected by

Related questions

1 votes
1 votes
1 answer
1
LavTheRawkstar asked Sep 9, 2018
1,030 views
Sort The Following Sequence of input using Heap sort.{ 10 , 2 , 1 , 5, 3 ,8 ,11,24 ,7 }Please show the output at every pass because i am getting confused.
1 votes
1 votes
1 answer
2
reena_kandari asked Jul 30, 2016
987 views
The number of elements that can be sorted in time using heap sort ?
1 votes
1 votes
1 answer
3
Himanshu1 asked Jan 20, 2016
1,269 views
What is the Best Case run time of Heap Sort ?A. $O(1)$B. $O(n)$C. $O(n \log n)$D. $O(\log n)$
0 votes
0 votes
0 answers
4
akash.dinkar12 asked Jun 27, 2019
307 views
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.