Heap Sort

Comparison-based sorting via Binary Heaps

Heap Sort uses a Binary Heap data structure. It works by first visualizing the array as a tree, building a Max Heap (where parent nodes are larger than children), and repeatedly extracting the maximum element to the end of the array.

Heap Size

Comparisons

Swaps

Press "Start Sorting" to begin

Current Root

Comparing

Swapping

Sorted Array

Heap Dynamics

Heap Sort is famous for being in-place while matching the performance of Merge Sort. It doesn't need extra arrays, making it memory-efficient $O(1)$ space.

Reliable Performance

Unlike Quick Sort, Heap Sort has no "worst-case" $O(n^2)$. It is guaranteed to finish in $O(n \log n)$ time regardless of the initial order.

Stability Note

Heap Sort is unstable. During the extraction phase, elements with the same value might swap their relative order because they are moved across the tree.

Complexity

Best/Average/Worst$O(n \log n)$

Space Complexity$O(1)$

Data StructureBinary Heap

In-PlaceYes

The Heapify Rule

Pseudocode

TypeScript

1function heapify(n, i) {
2  largest = i;
3  l = 2*i + 1;
4  r = 2*i + 2;
5  
6  if (l < n && arr[l] > arr[largest])
7    largest = l;
8  if (r < n && arr[r] > arr[largest])
9    largest = r;
10    
11  if (largest != i) {
12    swap(arr[i], arr[largest]);
13    heapify(n, largest);
14  }
15}

Use Case

Used in embedded systems where memory is tight and $O(n \log n)$ is required. Also used in Priority Queues.

Implementations

Python (In-Place)

Pseudocode

Python

1def heap_sort(arr):
2    n = len(arr)
3    # Build maxheap
4    for i in range(n // 2 - 1, -1, -1):
5        heapify(arr, n, i)
6    # Extract elements
7    for i in range(n-1, 0, -1):
8        arr[i], arr[0] = arr[0], arr[i]
9        heapify(arr, i, 0)
10 
11def heapify(arr, n, i):
12    largest = i
13    l = 2 * i + 1
14    r = 2 * i + 2
15    if l < n and arr[l] > arr[largest]:
16        largest = l
17    if r < n and arr[r] > arr[largest]:
18        largest = r
19    if largest != i:
20        arr[i], arr[largest] = arr[largest], arr[i]
21        heapify(arr, n, largest)

JavaScript

Pseudocode

JavaScript

1function heapSort(arr) {
2  const n = arr.length;
3  // Build max heap
4  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
5     heapify(arr, n, i);
6  }
7  // Extract
8  for (let i = n - 1; i > 0; i--) {
9    [arr[0], arr[i]] = [arr[i], arr[0]];
10    heapify(arr, i, 0);
11  }
12  return arr;
13}
14 
15function heapify(arr, n, i) {
16  let largest = i;
17  let l = 2 * i + 1;
18  let r = 2 * i + 2;
19  if (l < n && arr[l] > arr[largest]) largest = l;
20  if (r < n && arr[r] > arr[largest]) largest = r;
21  if (largest !== i) {
22    [arr[i], arr[largest]] = [arr[largest], arr[i]];
23    heapify(arr, n, largest);
24  }
25}

Heap Dynamics

Heap Sort is famous for being in-place while matching the performance of Merge Sort. It doesn't need extra arrays, making it memory-efficient $O(1)$ space.

Reliable Performance

Unlike Quick Sort, Heap Sort has no "worst-case" $O(n^2)$. It is guaranteed to finish in $O(n \log n)$ time regardless of the initial order.

Stability Note

Heap Sort is unstable. During the extraction phase, elements with the same value might swap their relative order because they are moved across the tree.

1function heapify(n, i) { 2 largest = i; 3 l = 2*i + 1; 4 r = 2*i + 2; 5 6 if (l < n && arr[l] > arr[largest]) 7 largest = l; 8 if (r < n && arr[r] > arr[largest]) 9 largest = r; 10 11 if (largest != i) { 12 swap(arr[i], arr[largest]); 13 heapify(n, largest); 14 } 15}

Implementations

Python (In-Place)

Pseudocode

Python

1def heap_sort(arr):
2    n = len(arr)
3    # Build maxheap
4    for i in range(n // 2 - 1, -1, -1):
5        heapify(arr, n, i)
6    # Extract elements
7    for i in range(n-1, 0, -1):
8        arr[i], arr[0] = arr[0], arr[i]
9        heapify(arr, i, 0)
10 
11def heapify(arr, n, i):
12    largest = i
13    l = 2 * i + 1
14    r = 2 * i + 2
15    if l < n and arr[l] > arr[largest]:
16        largest = l
17    if r < n and arr[r] > arr[largest]:
18        largest = r
19    if largest != i:
20        arr[i], arr[largest] = arr[largest], arr[i]
21        heapify(arr, n, largest)

JavaScript

Pseudocode

JavaScript

1function heapSort(arr) {
2  const n = arr.length;
3  // Build max heap
4  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
5     heapify(arr, n, i);
6  }
7  // Extract
8  for (let i = n - 1; i > 0; i--) {
9    [arr[0], arr[i]] = [arr[i], arr[0]];
10    heapify(arr, i, 0);
11  }
12  return arr;
13}
14 
15function heapify(arr, n, i) {
16  let largest = i;
17  let l = 2 * i + 1;
18  let r = 2 * i + 2;
19  if (l < n && arr[l] > arr[largest]) largest = l;
20  if (r < n && arr[r] > arr[largest]) largest = r;
21  if (largest !== i) {
22    [arr[i], arr[largest]] = [arr[largest], arr[i]];
23    heapify(arr, n, largest);
24  }
25}