Space complexity of heap sort

Question

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...

Comments

I think auxillary space required will be O(1) but no total space complexity,not sure.

Answer 1

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
}

Comments

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).

Answer 2

http://stackoverflow.com/questions/22233532/why-does-heap-sort-have-a-space-complexity-of-o1

Comments

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...............