October 28, 2023
October 28, 2023
October 28, 2023
###### Sorting
October 28, 2023
 Question 80
How much extra space is used by heapsort ?
 A O(1) B O(Log n) C O(n) D O(n​ 2​ )
Question 80 Explanation:
→ 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 intern takes no space. So, the space complexity of Heap Sort can be reduced to O(1)
→ The heapify function does not take O(logn) space, it will take O(logn) time in worst case. Here we don’t do heapify through any recursion call. We will do through iterative method and we don’t require any auxiliary space in this sorting. We use only input array.
So, we do heap sort in O(1) space complexity.
Question 80 Explanation:
→ 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 intern takes no space. So, the space complexity of Heap Sort can be reduced to O(1)
→ The heapify function does not take O(logn) space, it will take O(logn) time in worst case. Here we don’t do heapify through any recursion call. We will do through iterative method and we don’t require any auxiliary space in this sorting. We use only input array.
So, we do heap sort in O(1) space complexity.