Sorting Algorithms· 20 min

Heap Sort

Build a max-heap and extract maximums

Setup

Size20
Step 1 / 420

Current step

1 / 420

Action: Starting Heap Sort. We'll build a max-heap then repeatedly extract the max.

Why: This is the next operation required by the algorithm.

Result: The visualization now reflects this operation.

Step log

18
9
36
17
25
6
29
11
53
59
51
32
40
52
37
9
12
57
55
53
012345678910111213141516171819
Unsorted
Comparing
Swap needed
Swapping
Moving
Pivot
Sorted
heap.java
1void heapSort(int[] arr) {
2    int n = arr.length;
3    for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
4    for (int i = n - 1; i > 0; i--) {
5        int t = arr[0]; arr[0] = arr[i]; arr[i] = t;
6        heapify(arr, i, 0);
7    }
8}
9void heapify(int[] arr, int n, int i) {
10    int largest = i, l = 2*i + 1, r = 2*i + 2;
11    if (l < n && arr[l] > arr[largest]) largest = l;
12    if (r < n && arr[r] > arr[largest]) largest = r;
13    if (largest != i) {
14        int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
15        heapify(arr, n, largest);
16    }
17}
● Java

Heap Sort

Builds a max-heap from the input, then repeatedly swaps the root (max) with the last element and re-heapifies the reduced heap.

Time complexity
O(n log n)
Space
O(1)
Stable
No
Comparisons
116
n = 201 / 420 steps
11 / 46