Given an array of integers nums, sort the array in ascending order using the Heap Sort algorithm — first build a max-heap from the array (stored implicitly by index, no extra tree structure needed), then repeatedly swap the root (the current maximum) to the end of the unsorted region and re-heapify the shrinking heap.
nums = [8,4,3,7,6][3,4,6,7,8]Max-heap invariant: every parent is ≥ both its children, so index 0 is always the maximum of the current heap. Building the heap bottom-up (sift-down from the last non-leaf node down to the root) establishes this invariant in O(n). Each extraction swaps the known-maximum root to the end of the unsorted region — placing it in its final sorted position — then shrinks the heap and sifts the new root down in O(log n) to restore the invariant. Repeating this n-1 times yields an ascending sorted array, entirely in-place.
Repeatedly scanning for the maximum is selection sort, which is O(n²). A heap finds the maximum in O(log n).
First, turn the array into a max heap, so every parent is at least as big as its children. Build it bottom up by sifting down every parent, from the last one to the root. Now the largest value sits at index 0. Swap it with the last element of the heap, which is its final position, and shrink the heap. Sift the new root down to restore the heap, and repeat.
Build a max heap, then move the root to the end, again and again. In place, guaranteed n log n, but not stable.
Run the animation above on your own input, or watch the 1:47 video explanation of Heap Sort with a dry run and Java code.