Data Structures Questions
Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by first building a max heap from the given array, where the largest element is at the root. Then, it swaps the root element with the last element in the array, reducing the size of the heap by one. After that, it maintains the heap property by heapifying the reduced heap. This process is repeated until the array is sorted.
The time complexity of heap sort is O(n log n), where n is the number of elements in the array. This is because building the heap takes O(n) time, and for each element, the heapify operation takes O(log n) time. Therefore, the overall time complexity is O(n log n).