Build a max-heap in place, then repeatedly swap the root (max) to the end of the shrinking unsorted zone.
“Sort in O(n log n) with O(1) space / no recursion” → heap sort
Pattern 1: Heapify (build in O(n))
Sift down from the last parent back to the root:
void buildMaxHeap(int[] a) {
for (int i = a.length / 2 - 1; i >= 0; i--)
siftDown(a, i, a.length);
}
void siftDown(int[] a, int i, int n) {
while (true) {
int l = 2*i + 1, r = 2*i + 2, big = i;
if (l < n && a[l] > a[big]) big = l;
if (r < n && a[r] > a[big]) big = r;
if (big == i) return;
swap(a, i, big);
i = big;
}
}import heapq
# heapq is a MIN-heap — negate everything for a max-heap
def build_max_heap(a):
heap = [-x for x in a]
heapq.heapify(heap) # O(n) bottom-up
return [-x for x in reversed(heap)] # careful: see note// make_heap builds a max-heap by default
std::vector<int> v{4,10,3,5,1};
std::make_heap(v.begin(), v.end()); // O(n)function buildMaxHeap(a) {
for (let i = (a.length >> 1) - 1; i >= 0; i--) siftDown(a, i, a.length);
}
function siftDown(a, i, n) {
for (;;) {
const l = 2 * i + 1,
r = l + 1;
let big = i;
if (l < n && a[l] > a[big]) big = l;
if (r < n && a[r] > a[big]) big = r;
if (big === i) return;
[a[i], a[big]] = [a[big], a[i]];
i = big;
}
}Why O(n)? Half the nodes are leaves (0 work), and per-level work decays geometrically. Summing gives O(n), not O(n log n).
Pattern 2: Extract Loop
Build phase compacts the chaos into a heap; the extraction loop peels the max off one at a time. Press ▶.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Sort an Array — Max-Heap Ascending
Sort an array in O(n log n) time with O(1) extra space. Build a max-heap, then repeatedly swap the root (largest) to the end and sift down. The sorted region grows from right to left.
We sort [5,2,3,1] (LeetCode 912 Example 1) using heap sort. Phase 1: build a max-heap so the largest element (5) sits at the root. Phase 2: swap the root to the end of the unsorted zone, shrink the boundary, sift down. Watch the sorted region grow from right to left until the array is fully sorted.
1
# build max-heap
2
for i from n/2-1 down to 0:
3
siftDown(i)
4
5
# extract repeatedly
6
for end from n-1 down to 1:
7
swap(0, end) # max → its final place
8
siftDown(0, limit=end)
9
# ascending sort with a MAX-heap — root goes to the END
void heapSort(int[] a) {
buildMaxHeap(a);
for (int end = a.length - 1; end > 0; end--) {
swap(a, 0, end); // max -> final slot
siftDown(a, 0, end); // repair within [0..end)
}
}import heapq
def heap_sort(a):
heapq.heapify(a)
return [heapq.heappop(a) for _ in range(len(a))]
# min-heap pops ascending — same idea mirroredvoid heapSort(std::vector<int>& v) {
std::make_heap(v.begin(), v.end());
for (auto it = v.end(); it != v.begin(); --it) {
std::pop_heap(v.begin(), it); // max -> it-1
}
}function heapSort(a) {
buildMaxHeap(a);
for (let end = a.length - 1; end > 0; end--) {
[a[0], a[end]] = [a[end], a[0]];
siftDown(a, 0, end);
}
return a;
}Max-heap + swap-to-end produces ASCENDING order. Min-heap sorts descending (or pop into a new array ascending).
The sorted region grows from the RIGHT while the heap shrinks from the left — same array, two zones.
Common Mistakes
- Building with repeated
push(O(n log n)) instead of bottom-up heapify (O(n)) — fine but slower. - Sifting past the boundary after swaps (
limitmust shrink each round). - Expecting heap sort to be stable — equal elements get reordered.
- Min-heap + swap-to-end yields DESCENDING output.
Complexity
| Phase | Time | Space |
|---|---|---|
| Build | O(n) | O(1) |
| Extract ×n | O(n log n) | O(1) |
| Total | O(n log n) guaranteed | O(1) |
Premium Content
Unlock Heap Sort and all premium lessons with a subscription.
From ₹199.99/year — See plans