If we have n symble then we need to store each Symble in Array so
Space complexity = O(n)
Space complexity does includes input space.
Also,input will be array of characters along with frequencies.
Can we convert it to minheap inplace?
Space = n + long = o (logn) .It is 0(n).May be typeo
Please tell how will we create min heap without extra space?
I didn't know the difference between auxiliary space complexity and space complexity. Thanks for sharing. And heapsort is inplace because of this:
"Space Complexity of an algorithm" means extra space(memory) that is needed by the algorithm
@Akash , Good question !
Max-Heapify uses tail recursion because function call is at the end. Due to this tail recursion , it minimizes the space complexity of heap-sort to O(1).
So, Space Complexity of Heap-Sort is O(1).
To understand , how space complexity becomes O(1) using tail-recursion .
watch this video and then apply max-heapify algorithm for the below example and observe the space complexity using stack method.
other link :- https://stackoverflow.com/questions/72209/recursion-or-iteration
2nd thing is , we can also convert this recursive max-heapify procedure to iterative procedure which will take O(1) space.
I have given the link of University of Texas where it is mentioned that :-
We often speak of "extra" memory needed, not counting the memory needed to store the input itself.
So, we should not have to consider the input size to find the space complexity of an algorithm.
@Akash ,it should be O(n) which you have already mentioned because we have to store frequencies of characters from the input file seperately in the array.