Heap Sort

Heap sort is a comparison-based sorting technique based on the Binary Heap It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.

Uses a binary heap data structure to sort elements in an array

Make sure to understand the Heapify operation.

Pseudocode

• Build the heap - Heapify: means arranging the elements in a way that each node is greater than or equal to its child nodes. Ensure max is at the root
• Extract Max Element: After building the heap, the maximum element (at the root) is swapped with the last element of the array. We decrease the heap size by 1, excluding the last element from future consideration. This step effectively places the maximum element at its correct position at the end of the array.
• Restore the heap property: To maintain the heap property, we perform heapify on the root node to adjust the elements and restore the max-heap property. This step ensures that the new root contains the maximum element among the remaining elements.
• Repeat steps 2 and 3: Steps 2 and 3 are repeated until all elements are extracted from the heap. In each iteration, the maximum element is extracted and placed at the end of the array, while the remaining elements are adjusted to maintain the heap property.
• Final sorted array: Once all elements are extracted and the heap size becomes 0, the array is sorted in ascending order. The extracted elements, placed at the end of the array in each iteration, form the sorted sequence.

$\to$ does not require more memory space beyond the input array. $\to$ not stable

Time Complexity: For loop takes \Theta(n)$$ and while loop takes O(n\log n)$.