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). Algorithms space-complexity sorting heap-sort + – Suryakant asked Jun 30, 2017 retagged Jun 21, 2022 by makhdoom ghaya Suryakant 679 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Akriti sood commented Jul 1, 2017 reply Follow Share space complexity is taken as only "extra space" needed,not the size of input data. 0 votes 0 votes joshi_nitish commented Jul 1, 2017 reply Follow Share it will be O(1).. 0 votes 0 votes Akriti sood commented Jul 1, 2017 reply Follow Share @nitish,we need space for the stack while making recursion calls. 0 votes 0 votes joshi_nitish commented Jul 1, 2017 reply Follow Share in heap sort no recursion is used...heap implementation is purely based on array and only interative technique is used....so it will be O(1).. 0 votes 0 votes Akriti sood commented Jul 1, 2017 reply Follow Share when u will use heapify() function in heap() sort then ,u will call heapify() recursively 0 votes 0 votes joshi_nitish commented Jul 1, 2017 reply Follow Share 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 votes 1 votes Akriti sood commented Jul 1, 2017 reply Follow Share http://www.geeksforgeeks.org/heap-sort/ pls see the code for heapify()here. 0 votes 0 votes joshi_nitish commented Jul 1, 2017 reply Follow Share 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 votes 1 votes Please log in or register to add a comment.
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) Mohitkumaraiactr answered Jul 1, 2017 Mohitkumaraiactr comment Share Follow See all 0 reply Please log in or register to add a comment.