Heap Sort builds a binary heap data structure from the array and then
repeatedly extracts the maximum element from the heap until it is empty,
thereby obtaining a sorted array.
Time Complexity
The time complexity of the heap sort algorithm is O(n log n), where n is the
number of elements in array. This complecity is applicable for the best,
average, and wors case scenarios.
Bulding initial Heap: O(n)
Heapify process during extraction: O(log n)
Repeated heapify process for each element: O(n)
Combining those, we get total time complexity of O(n log n)
Heap Sort builds a binary heap data structure from the array and then repeatedly extracts the maximum element from the heap until it is empty, thereby obtaining a sorted array.
Time Complexity
The time complexity of the heap sort algorithm is O(n log n), where n is the number of elements in array. This complecity is applicable for the best, average, and wors case scenarios.
Bulding initial Heap: O(n)
Heapify process during extraction: O(log n)
Repeated heapify process for each element: O(n)
Combining those, we get total time complexity of O(n log n)
Space complexity: O(1)