265. Sort an Array Using Heap Sort

Given an array of n integers, sort it in ascending order using the heap sort algorithm (build a max-heap from the array, then repeatedly swap the heap's root with the last unsorted element and sift down to restore the heap) and print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print the array sorted in ascending order, space-separated.

1 <= n <= 10^5

Heap sort is one of the few O(n log n) sorting algorithms that is also truly IN-PLACE (O(1) extra space) - a valuable, specific tradeoff worth mentioning when comparing sorting algorithms' space/time characteristics.

Sort an array in ascending order using the heap sort algorithm: build a max-heap, then repeatedly extract the maximum. Brute force: Use any other general sorting algorithm (like a simple selection sort, repeatedly scanning for the maximum directly) - this achieves the same result but costs O(n²), since finding the maximum via a linear scan each time is slower than maintaining a heap structure. Optimised: Maintaining the unsorted region as a max-heap means finding (and removing) the current maximum is always O(log n) (via sift-down), rather than O(n) with a linear scan - repeating this n times gives O(n log n) overall, matching the best comparison-based sorting algorithms, all done IN PLACE with O(1) extra space.

Build a max-heap in place by sifting down every non-leaf node, working from the middle of the array to the root, which arranges the array so the largest element sits at index 0. Then repeatedly swap the root (current maximum) with the last element of the still-unsorted region, shrink that region by one, and sift down the new root to restore the max-heap property. Heap construction takes linear time and each of the n extractions costs O(log n) to restore the heap, and since everything happens by swapping within the original array, no extra array is needed. Time: O(n log n) Space: O(1)

Repeatedly scan the unsorted portion of the array to find its maximum element and swap it into the last position of the unsorted portion, shrinking that region by one after each pass. This is the simplest possible sorting strategy: n passes, each doing a linear scan for the maximum, giving quadratic time overall. It sorts entirely in place with no extra memory. Time: O(n^2) Space: O(1)

Recursively split the array into halves, sort each half independently, and merge the two sorted halves back together in linear time using an auxiliary buffer. Merge sort guarantees O(n log n) time in every case since the split is always balanced, at the cost of needing extra space proportional to the array size during the merge step. Time: O(n log n) Space: O(n)

1. Build a max-heap IN PLACE from the whole array (heapify from the last non-leaf node up to the root). 2. Repeatedly swap the root (the current maximum) with the LAST element of the currently-unsorted region, then shrink that region by one. 3. Sift down the new root to restore the max-heap property, and repeat until the unsorted region is empty.

Time: O(n log n) - building the initial heap takes O(n), and each of the n extractions costs O(log n). Space: O(1) extra space - the entire sort happens within the original array.

n = 1 (already sorted), an already-sorted or fully reverse-sorted array, and n = 10^5 to confirm O(n log n) performance.

Be ready to highlight heap sort's key advantage over quicksort/mergesort: guaranteed O(n log n) worst case AND O(1) extra space, unlike quicksort's O(n²) worst case or mergesort's O(n) extra space - though heap sort is typically slower in practice due to poor cache locality.