5,808 views
9 votes
9 votes
Why space complexity of heapsort is O(1)....and why not O(logn)..because of space required by recursion calls which is equivalent to height of the tree...where am i getting wrong plz help...

2 Answers

Best answer
9 votes
9 votes

HEAP SORT uses MAX_HEAPIFY function which calls itself but it can be made using a simple while loop and thus making it an iterative function which inturn takes no space and hence Space Complexity of HEAP SORT can be reduced to O(1).

while ( i < = heapsize) {
 lc <- left(i)
 rc <- right(i)
 if (lc<=heapsize) and (A[lc]>A[i])
  largest <- lc
 else
  largest <- i 
 if (rc<=heapsize) and (A[rc]>A[largest])
  largest <- rc
 if (largest != i)
 {
   exchange A[i] <-> A[largest]
   i <- largest
 } 
 else
  break
}
selected by
0 votes
0 votes

Related questions

1 votes
1 votes
1 answer
3
reena_kandari asked Jul 30, 2016
987 views
The number of elements that can be sorted in time using heap sort ?