1. Array size
n is the full heap size before extraction begins.
const n = arr.lengthTyporithm · hard
Heap Sort
▷ Interactive algorithm labheap-sortsortingheapselectionin-place
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Heap Sort
Sorting Algorithms
Heap Sort builds a max heap, repeatedly moves the largest value to the end, and restores the heap.
A max heap keeps the largest value at index 0.
The build phase heapifies parent nodes from the bottom up.
The extraction phase swaps the root with the last unsorted value.
After each swap, the heap size shrinks and heapify restores the max-heap property.
Heap Sort is in-place and O(n log n), but it is not stable by default.
Preparing algorithm lab…
01
Build a max heap first.
02
Swap the root into the sorted tail.
03
Heapify the smaller heap after each extraction.
04
O(n log n) time in all main cases.
05
O(1) extra space, unstable by default.
function heapSort(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (let end = n - 1; end > 0; end--) {
[arr[0], arr[end]] = [arr[end], arr[0]];
heapify(arr, end, 0);
}
return arr;
}
function heapify(arr, heapSize, root) {
let largest = root;
const left = 2 * root + 1;
const right = 2 * root + 2;
if (left < heapSize && arr[left] > arr[largest]) largest = left;
if (right < heapSize && arr[right] > arr[largest]) largest = right;
if (largest !== root) {
[arr[root], arr[largest]] = [arr[largest], arr[root]];
heapify(arr, heapSize, largest);
}
}Read the implementation
Connect each part of the code to the concept before you type.
2. Build max heap
Start from the last parent and heapify upward to build a max heap.
for (let i = Math.floor(n / 2) - 1; i >= 0; i--)3. Extract max
Each pass moves the current largest value to the end.
for (let end = n - 1; end > 0; end--)4. Swap root to end
The max heap root is swapped into its final sorted position.
[arr[0], arr[end]] = [arr[end], arr[0]]5. Shrink heap
Heapify only the remaining unsorted prefix.
heapify(arr, end, 0)6. Largest candidate
Start by assuming the root is already the largest among parent and children.
let largest = root7. Left child index
Array heaps compute the left child from the parent index.
const left = 2 * root + 18. Right child check
The right child can replace the largest candidate if it exists and is greater.
right < heapSize && arr[right] > arr[largest]9. Restore below
After swapping, heapify continues where the moved value landed.
heapify(arr, heapSize, largest)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.