DSA · Reimagined
JSON All
Sorting hard time O(n log n) space O(1)

Heap Sort

Treat the array as a binary heap (children of i live at 2i+1 and 2i+2). Build a max-heap so the biggest value is at the front, swap it to the end, shrink the heap, and sift the new root down. Repeat.

4
0
10
1
3
2
5
3
1
4
8
5
2
6
7
7

Heap sort: first arrange the array into a max-heap.

1 / 37

Practice

Machine twin: /dsa-viz-v2/heap-sort.json — the full deterministic run as structured data.