UGC NET CSE | December 2004 | Part 2 | Question: 25

Question

How much extra space is used by heapsort ?

• A. $O (1)$
• B. $O (\log n)$
• C. $O (n)$
• D. $O (n^2)$

Answer 1

Answer should be option A because heapsort in an inplace sorting technique and it doesn't require any extra space it uses the same array for sorting purpose

Comments

Can you do heapsort without recursion?

---

Yes sir it's possible

Max heap:

while ( i < = heapsize) {
 le <- left(i)
 ri <- right(i)
 if (le<=heapsize) and (A[le]>A[i])
  largest <- le
 else
  largest <- i 
 if (ri<=heapsize) and (A[ri]>A[largest])
  largest <- ri
 if (largest != i)
 {
   exchange A[i] <-> A[largest]
   i <- largest
 } 
 else
  break
}