in Algorithms retagged by
399 views
0 votes
0 votes
Space complexity = input size + extra space

So, heap sort also takes input of an 'n' size array.

Does this mean that space cost of heap sort algo is O (n).
in Algorithms retagged by
399 views

4 Comments

we will run heapify from index= floor(n/2) to 1...there is no need of recursion...everything can be done using for and while loops..
1
1
http://www.geeksforgeeks.org/heap-sort/
pls see the code for heapify()here.
0
0

heapify can be performed by both iterative and recursive way...but the best among two is iterartive since it give less space complexity(O(1)) then reccursive (O(logn))...

1
1

1 Answer

0 votes
0 votes
Space complexity in heap sort will be height of the stack and for n number of nodes in complete or almost complete binary tree height would be logn so space complexity should be O(logn)

Related questions

1 vote
1 vote
3 answers
2