Heap Sort

Example 1

Input: arr[] = [3, 5, 1, 10, 2, 7]

Output: [1, 2, 3, 5, 7, 10]

Explanation: Heap sort is applied to the array by first constructing a max heap. Then, the root element (maximum value) is swapped with the last element in the heap and the heap size is reduced. The process continues until all elements are sorted. The sorted array is [1, 2, 3, 5, 7, 10].

Example 2

Input: arr[] = [10, 20, 5, 6, 1, 8]

Output: [1, 5, 6, 8, 10, 20]

Explanation: After applying heap sort to the array, the elements are rearranged in ascending order. The heap sort process involves building a max heap and then performing swaps, followed by reducing the heap size. The final sorted array is [1, 5, 6, 8, 10, 20].