Heap Sort

comparisonin-placeunstable

Press play to start

1function heapSort(arr: number[]): number[] {
const n = arr.length
for (let i = Math.floor(n/2)-1; i >= 0; i--)
  heapify(arr, n, i)
for (let i = n-1; i > 0; i--) {
  [arr[0], arr[i]] = [arr[i], arr[0]]
  heapify(arr, i, 0)
}
return arr
10}
11function heapify(arr: number[], n: number, i: number) {
let largest = i
const l = 2*i+1, r = 2*i+2
if (l < n && arr[l] > arr[largest]) largest = l
if (r < n && arr[r] > arr[largest]) largest = r
if (largest !== i) {
  [arr[i], arr[largest]] = [arr[largest], arr[i]]
  heapify(arr, n, largest)
}
20}

Step 1/0

Custom array:

Complexity

Best:O(n log n)
Average:O(n log n)
Worst:O(n log n)
Space:O(1)

Description

Builds a max-heap from the array, then repeatedly extracts the maximum element and places it at the end, rebuilding the heap each time.

When to use

Guaranteed O(n log n) worst case with O(1) space. Use when worst-case performance is critical and space is constrained.