15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Heap sort builds a max-heap inside the array, then repeatedly swaps the root with the last heap position and sifts the new root down. Each swap fixes one maximum at the end, so the sorted suffix grows from right to left. It runs in O(n log n) time with O(1) extra space and is not stable.
| Build the heap | O(n), sift down from the last parent (n // 2) - 1 to the root |
|---|---|
| Extraction | n - 1 rounds, each one swap plus an O(log n) sift-down |
| Total time | O(n log n) |
| Extra space | O(1), sorts in place |
| Stable | No, swaps can reorder equal values |
| Zero-based indices | left 2i + 1, right 2i + 2, parent (i - 1) // 2 |
Heap Sort produces an array with the same values as the input, arranged in ascending order. The lesson also assumes you have seen an in-place sorting method such as Selection Sort.
Heap Sort uses one array in two roles:
A max-heap is a complete binary tree where every parent is at least as large as either existing child.
For a zero-based array index i:
(i - 1) // 2, when i > 02i + 12i + 2The array stores the tree level by level. No node objects or pointers are needed.
For sorting-property context, see Elementary Sorts.
Use this array throughout:
1index: 0 1 2 3
2value: [3, 1, 4, 2]Its array positions represent this complete binary tree:
1 index 0: 3
2 / \
3 index 1: 1 index 2: 4
4 /
5index 3: 2The tree is not yet a max-heap:
0, value 3 is smaller than its right child, 4.1, value 1 is smaller than its left child, 2.To repair a node whose children are already heaps, move that node downward. This operation is called sift-down.
Leaves do not need repair. A leaf has no children, so it already satisfies max-heap order.
For an array of length 4, the last parent is:
1(4 // 2) - 1 = 1Start at index 1, then move backward to index 0.
Heap Sort on [3, 1, 4, 2]: sift down index 1 then 0 to build the max-heap [4, 2, 3, 1], then swap the root to the end, shrink the heap and sift down, until [1, 2, 3, 4].
At index 1:
1.2(1) + 1 = 3, with value 2.4 is outside the array.1 with its larger existing child, 2.Index 3 is now a leaf. Sift-down ends.
At index 0:
1, value 2.2, value 4.4 at index 2.3 < 4, swap them.Index 2 is a leaf. Heap construction is complete.
1max-heap: [4, 2, 3, 1]The root is 4, the largest value in the heap.
Swap the root with the last active heap position. The maximum moves into its final sorted position.
Swap index 0 and index 3.
The active heap is now indices 0..2. The sorted suffix is [4].
The root value 1 must sift down:
2 and 3.3.1 and 3.The active prefix is again a max-heap.
Swap the root with index 2.
The active heap is indices 0..1.
Sift down the root:
0 has only a left child at index 1.1 with 2.Swap index 0 and index 1.
The active heap is only index 0, a single value. The full array is sorted.
1[1, 2, 3, 4]After heap construction, the active array prefix is a max-heap.
During extraction, keep two regions separate:
1[ active max-heap | sorted suffix ]The condition that remains true after each completed extraction is:
The active prefix is a valid max-heap. The suffix starting at
heapSizecontains extracted maximum values in ascending order. Every value in that suffix is at least every value still in the active heap.
For example, after the first extraction and repair:
1[3, 2, 1 | 4][3,2,1] is a max-heap.[4] is sorted.4.After the second extraction and repair:
1[2, 1 | 3, 4][2,1] is a max-heap.[3,4] is sorted.The boundary limits sift-down. The helper must receive the current heapSize so it never changes a value that has already entered the sorted suffix.
Suppose a node may be smaller than one of its children, but both child subtrees are already max-heaps.
Choosing the larger child preserves heap order. Moving the parent below the smaller child while a larger child remains above it leaves heap order broken.
A parent can be repaired only after its children already root valid heaps.
Therefore:
(n // 2) - 1.Bottom-up repair turns the unordered array into a max-heap.
Once the array is a max-heap:
heapSize by one.The sorted part grows from the right side of the array.
heapSize is an exclusive boundary: active heap indices are 0 through heapSize - 1.
11 procedure siftDown(A, heapSize, root) -> nothing
22 # Input: A is mutable; 0 <= root < heapSize.
33 # Contract: child subtrees of root are max-heaps.
44 # Mutation: rearranges only A[0 .. heapSize - 1].
55 # Result: A[0 .. heapSize - 1] is a max-heap at and below root.
6
76 while 2 * root + 1 < heapSize
87 left <- 2 * root + 1
98 right <- 2 * root + 2
109 largerChild <- left
11
1210 if right < heapSize and A[right] > A[left]
1311 largerChild <- right
14
1512 if A[root] >= A[largerChild]
1613 return
17
1814 swap A[root], A[largerChild]
1915 root <- largerChild
20
2116 procedure heapSort(A) -> A
2217 # Input: mutable array A of comparable values.
2318 # Mutation: rearranges A in place into ascending order.
2419 # Return value: the same array A, now sorted.
25
2620 n <- length(A)
27
2821 lastParent <- (n // 2) - 1
2922 for parent <- lastParent down to 0
3023 siftDown(A, n, parent)
31
3224 for heapSize <- n - 1 down to 1
3325 swap A[0], A[heapSize]
3426 siftDown(A, heapSize, 0)
35
3627 return AThe helper never examines index heapSize or beyond. Those positions are already part of the sorted suffix.
Start with:
1A = [3, 1, 4, 2]
2n = 4Line 20
1n = 4Line 21
1lastParent = (4 // 2) - 1 = 1Line 22: first loop value is parent = 1.
Line 23: call siftDown(A, 4, 1).
Inside siftDown:
2(1) + 1 = 3 < 4, so continue.left = 3.right = 4.largerChild = 3.right < heapSize is 4 < 4, false. There is no right child.A[1] >= A[3] is 1 >= 2, false.A[1] and A[3].1A = [3, 2, 4, 1]root = 3.2(3) + 1 = 7 < 4 is false. Return from the helper.Line 22: next loop value is parent = 0.
Line 23: call siftDown(A, 4, 0).
2(0) + 1 = 1 < 4, so continue.left = 1.right = 2.largerChild = 1.2 < 4 and A[2] > A[1] is 4 > 2, true.largerChild = 2.A[0] >= A[2] is 3 >= 4, false.A[0] and A[2].1A = [4, 2, 3, 1]root = 2.2(2) + 1 = 5 < 4 is false. Return.Heap construction has produced:
1A = [4, 2, 3, 1]Line 24: first loop value is heapSize = 3.
Line 25: swap A[0] and A[3].
1A = [1, 2, 3, 4]
2active heap: indices 0..2
3sorted suffix: index 3Line 26: call siftDown(A, 3, 0).
1 < 3, continue.left = 1.right = 2.largerChild = 1.2 < 3 and A[2] > A[1] is 3 > 2, true.largerChild = 2.A[0] >= A[2] is 1 >= 3, false.A[0] and A[2].1A = [3, 2, 1, 4]root = 2.5 < 3 is false. Return.Line 24: next loop value is heapSize = 2.
Line 25: swap A[0] and A[2].
1A = [1, 2, 3, 4]
2active heap: indices 0..1
3sorted suffix: indices 2..3Line 26: call siftDown(A, 2, 0).
1 < 2, continue.left = 1.right = 2.largerChild = 1.2 < 2 is false. There is only a left child.A[0] >= A[1] is 1 >= 2, false.A[0] and A[1].1A = [2, 1, 3, 4]root = 1.3 < 2 is false. Return.Line 24: next loop value is heapSize = 1.
Line 25: swap A[0] and A[1].
1A = [1, 2, 3, 4]Line 26: call siftDown(A, 1, 0).
1 < 1 is false. Return immediately.The loop ends. Line 27 returns:
1[1, 2, 3, 4]Assume the left and right child subtrees of root are already max-heaps.
If A[root] is at least its larger existing child, it is also at least the other child. Heap order holds at root, so the helper can stop.
Otherwise, the algorithm swaps A[root] with the larger child.
The helper repeats along this one downward path. It either stops when order holds or reaches a leaf. Therefore, sift-down restores max-heap order along the affected path.
Heapify processes parents from the last parent backward to the root.
When processing one parent, every node below it has already been processed or is a leaf. Therefore, its child subtrees are max-heaps. The sift-down argument applies and makes this parent’s subtree a max-heap.
After processing index 0, the root’s subtree is the entire array. Thus, the full array is a max-heap.
In a max-heap, every parent is at least each child. Following parent-child relationships from the root down to any active node shows that the root is at least that node.
So the root is a maximum value of the active heap.
Before an extraction:
The root is the maximum active value. Swapping it with the final active position places that maximum immediately before the old suffix.
It is no larger than the old first suffix value, because every old suffix value was already at least every active value. So the new, longer suffix remains ascending.
The swap may disrupt max-heap order at the root of the reduced active prefix. Sift-down restores it without touching the suffix because it uses the reduced heapSize.
Thus the condition is preserved after every extraction.
Initially, heapify establishes the active max-heap and the suffix is empty. When the extraction loop terminates, the active heap has at most one value, and the suffix contains all values in ascending order. Therefore, the entire array is sorted.
A single sift-down follows one parent-to-child path.
A complete binary heap has height proportional to log n, so one sift-down performs at most O(log n) downward moves and comparisons.
Heap construction costs O(n):
Adding the possible downward movement across all nodes in bottom-up heapify gives O(n) total work.
The extraction loop runs n - 1 times:
1heapSize = n - 1, n - 2, ..., 1Each iteration performs one root-end swap and one O(log n) sift-down. The extraction work is therefore:
1(n - 1) · O(log n) = O(n log n)Adding heap construction gives:
1O(n) + O(n log n) = O(n log n)The algorithm uses:
So its auxiliary space is O(1).
Basic in-place Heap Sort does not promise stability. Equal values can change relative order during swaps.
Incorrect assumption
1left = 2 * root
2right = 2 * root + 1These formulas are for a one-based heap, not a zero-based array.
Input that exposes it
1[1, 3, 2]At root index 0, the incorrect formula produces child indices 0 and 1. It treats the root as its own child and does not treat index 2 as the root’s right child.
Correction
1left = 2 * root + 1
2right = 2 * root + 2The real children of zero-based index 0 are indices 1 and 2.
Incorrect line
1largerChild = leftwith no comparison against the right child.
Input that exposes it
1[1, 2, 3]Swapping with the left child produces:
1[2, 1, 3]But 2 is still smaller than its right child, 3. The result is not a max-heap.
Correction
When the right child exists, compare both children and choose the larger one.
1if right < heapSize and A[right] > A[left]
2 largerChild = rightIncorrect call
1siftDown(A, length(A), 0)after every root-end swap.
Input that exposes it
After the first extraction from the lesson example:
1[1, 2, 3, 4]The active heap should be only indices 0..2. If sift-down uses the full length, it can compare against 4 and move it back into the heap:
1[4, 2, 3, 1]The sorted suffix has been disturbed.
Correction
Pass the reduced exclusive boundary:
1siftDown(A, heapSize, 0)Incorrect approach
1siftDown(A, n, 0)performed once on an unordered array.
Input that exposes it
1[1, 4, 3, 2]A root sift-down swaps 1 with 4:
1[4, 1, 3, 2]The root now looks valid, but index 1 still violates heap order because 1 < 2.
Correction
Repair every parent from the last parent backward to the root:
1for parent <- (n // 2) - 1 down to 0
2 siftDown(A, n, parent)| Input | Required result or behavior |
|---|---|
[] | Already sorted; loops perform no work. |
[6] | Already sorted; no extraction occurs. |
[1,2,3] | Heapifies, then returns [1,2,3]. |
[3,3,3] | Returns [3,3,3]; equal values have no stability guarantee. |
[2,1] | Swaps the root to the end and returns [1,2]. |
| A node with only a left child | Compare only that existing child; do not read a nonexistent right-child index. |
Implement in-place ascending Heap Sort with zero-based max-heap indices and a heapSize-limited siftDown helper.
The executable tests verify sorted permutations for:
1
2def sift_down(a, heap_size, root): # heap_size is an exclusive boundary
3 while 2 * root + 1 < heap_size:
4 left = 2 * root + 1
5 right = 2 * root + 2
6 larger = left
7 if right < heap_size and a[right] > a[left]:
8 larger = right
9 if a[root] >= a[larger]:
10 return
11 a[root], a[larger] = a[larger], a[root]
12 root = larger
13
14def build_max_heap(a):
15 n = len(a)
16 for parent in range(n // 2 - 1, -1, -1): # last parent down to the root
17 sift_down(a, n, parent)
18
19def heap_sort(a):
20 build_max_heap(a)
21 for heap_size in range(len(a) - 1, 0, -1):
22 a[0], a[heap_size] = a[heap_size], a[0] # max joins the sorted suffix
23 sift_down(a, heap_size, 0) # repair inside the shrunken heap
24 return a
25
26nums = [3, 1, 4, 2]
27heap = nums[:]
28build_max_heap(heap)
29print("max-heap:", heap)
30print("sorted:", heap_sort(nums))1
2import java.util.Arrays;
3
4public class Main {
5 static void siftDown(int[] a, int heapSize, int root) { // heapSize is an exclusive boundary
6 while (2 * root + 1 < heapSize) {
7 int left = 2 * root + 1;
8 int right = 2 * root + 2;
9 int larger = left;
10 if (right < heapSize && a[right] > a[left]) larger = right;
11 if (a[root] >= a[larger]) return;
12 int tmp = a[root]; a[root] = a[larger]; a[larger] = tmp;
13 root = larger;
14 }
15 }
16
17 static void buildMaxHeap(int[] a) {
18 int n = a.length;
19 for (int parent = n / 2 - 1; parent >= 0; parent--) { // last parent down to the root
20 siftDown(a, n, parent);
21 }
22 }
23
24 static int[] heapSort(int[] a) {
25 buildMaxHeap(a);
26 for (int heapSize = a.length - 1; heapSize >= 1; heapSize--) {
27 int tmp = a[0]; a[0] = a[heapSize]; a[heapSize] = tmp; // max joins the sorted suffix
28 siftDown(a, heapSize, 0); // repair inside the shrunken heap
29 }
30 return a;
31 }
32
33 public static void main(String[] args) {
34 int[] nums = {3, 1, 4, 2};
35 int[] heap = nums.clone();
36 buildMaxHeap(heap);
37 System.out.println("max-heap: " + Arrays.toString(heap));
38 System.out.println("sorted: " + Arrays.toString(heapSort(nums)));
39 }
40}1
2#include <iostream>
3#include <utility>
4#include <vector>
5using namespace std;
6
7void siftDown(vector<int>& a, int heapSize, int root) { // heapSize is an exclusive boundary
8 while (2 * root + 1 < heapSize) {
9 int left = 2 * root + 1;
10 int right = 2 * root + 2;
11 int larger = left;
12 if (right < heapSize && a[right] > a[left]) larger = right;
13 if (a[root] >= a[larger]) return;
14 swap(a[root], a[larger]);
15 root = larger;
16 }
17}
18
19void buildMaxHeap(vector<int>& a) {
20 int n = a.size();
21 for (int parent = n / 2 - 1; parent >= 0; parent--) { // last parent down to the root
22 siftDown(a, n, parent);
23 }
24}
25
26void heapSort(vector<int>& a) {
27 buildMaxHeap(a);
28 for (int heapSize = (int)a.size() - 1; heapSize >= 1; heapSize--) {
29 swap(a[0], a[heapSize]); // max joins the sorted suffix
30 siftDown(a, heapSize, 0); // repair inside the shrunken heap
31 }
32}
33
34void print(const char* label, const vector<int>& a) {
35 cout << label << " [";
36 for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
37 cout << "]" << endl;
38}
39
40int main() {
41 vector<int> nums = {3, 1, 4, 2};
42 vector<int> heap = nums;
43 buildMaxHeap(heap);
44 print("max-heap:", heap);
45 heapSort(nums);
46 print("sorted:", nums);
47}1
2function siftDown(a, heapSize, root) { // heapSize is an exclusive boundary
3 while (2 * root + 1 < heapSize) {
4 const left = 2 * root + 1;
5 const right = 2 * root + 2;
6 let larger = left;
7 if (right < heapSize && a[right] > a[left]) larger = right;
8 if (a[root] >= a[larger]) return;
9 [a[root], a[larger]] = [a[larger], a[root]];
10 root = larger;
11 }
12}
13
14function buildMaxHeap(a) {
15 const n = a.length;
16 for (let parent = Math.floor(n / 2) - 1; parent >= 0; parent--) { // last parent down to the root
17 siftDown(a, n, parent);
18 }
19}
20
21function heapSort(a) {
22 buildMaxHeap(a);
23 for (let heapSize = a.length - 1; heapSize >= 1; heapSize--) {
24 [a[0], a[heapSize]] = [a[heapSize], a[0]]; // max joins the sorted suffix
25 siftDown(a, heapSize, 0); // repair inside the shrunken heap
26 }
27 return a;
28}
29
30const nums = [3, 1, 4, 2];
31const heap = [...nums];
32buildMaxHeap(heap);
33console.log(`max-heap: [${heap.join(', ')}]`);
34console.log(`sorted: [${heapSort(nums).join(', ')}]`);Heapify turns an unordered array into a heap. Bottom-up, you sift down every parent from index (n // 2) - 1 back to 0, so each node's children already root valid heaps when you reach it. [3, 1, 4, 2] becomes [4, 2, 3, 1].
O(n log n). Building the heap costs O(n), because most nodes are leaves or sit near them. The n - 1 extractions each cost one O(log n) sift-down.
The root of a max-heap is the largest active value. Swapping it into the last active slot puts that value in its final place, and the sorted suffix grows from the right.
No. The root-to-end swap jumps over equal values, so equal keys can change relative order. With tagged records, equal keys can come out in a different order than they went in.
The sorted suffix must stay untouched. With a full-length boundary, sift-down could pull sorted values back into the heap. Passing the reduced heapSize keeps it inside the active prefix.
Heap sort guarantees O(n log n) with O(1) extra space. Quick sort is O(n^2) in the worst case, but its partition scans memory sequentially, which is why it is often faster in practice. Neither is stable.