← Back to DSA Animator
Heap Sort LC #912 Medium Binary Heap
Problem

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.

Example 1
Input: nums = [8,4,3,7,6]
Output: [3,4,6,7,8]
Constraints: 1 ≤ n ≤ 5*10^4  |  -5*10^4 ≤ nums[i] ≤ 5*10^4  |  The heap is stored implicitly in this flat array — for any index i, its children live at 2i+1 and 2i+2.
Try Examples
Custom:
Approach
Build a Max-Heap, Then Repeatedly Extract the Max
The heap is stored implicitly in this flat array — for index i, children live at 2i+1 and 2i+2. Bottom-up sift-down from the last non-leaf node builds a max-heap in O(n). Then repeatedly swap the root (max) with the last unsorted element, shrink the heap, and sift-down the new root. O(n log n) time, O(1) space.
Array
Heap Root Comparing Swapping Sorted
nums[] — current state (implicit heap: children of i are at 2i+1, 2i+2)
Variables
phase
—
root
—
comparisons
0
swaps
0
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Build a max-heap in-place (bottom-up sift-down from the last non-leaf node)
2
Swap the root (max) with the last unsorted element
3
Shrink the heap by one and sift-down the new root to restore the heap property
4
Repeat until the heap has one element left
Best
O(n log n)
Avg/Worst
O(n log n)
Space
O(1)
Why It Works

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.