471 views
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...
I think auxillary space required will be O(1) but no total space complexity,not sure.

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
}

answered by Junior (577 points) 1 2 6
yes, i am agree with the kamal.

since, recursive algorithm can be implemented using loops thats why we dont consider stack in  space complexity of the algoritm thats why O(1)
Yes, We can implement HEAPIFY() recursive algorithm using loop, so no stack is required.
Space complexity would be O(1).
answered by Boss (6.4k points) 4 23 49
I have already seen this answer. But I am still not getting why space required by recursion calls is not considered.
very nice question. i have the same doubt.. It should be log n because every time we are calling  heapify on the root of tree?  experts advice needed...............