jsschools

Heap Sort

Builds a max-heap from the array, then repeatedly extracts the maximum to produce a sorted result in-place.

Spec ↗

Syntax

heapSort(arr)

Parameters

NameTypeRequiredDescription
arr Array<number> Yes The mutable array of numbers to sort in-place.

Returns

void — Sorts the input array in-place; returns nothing.

Examples

function heapify(arr, n, i) {
  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);
  }
}

function heapSort(arr) {
  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);
  }
}

const nums = [12, 11, 13, 5, 6, 7];
heapSort(nums);
console.log(nums);
Output 
[ 5, 6, 7, 11, 12, 13 ]

// Works correctly on duplicate values
function heapSort(arr) {
  const n = arr.length;
  const heapify = (n, i) => {
    let lg = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[lg]) lg = l;
    if (r < n && arr[r] > arr[lg]) lg = r;
    if (lg !== i) { [arr[i], arr[lg]] = [arr[lg], arr[i]]; heapify(n, lg); }
  };
  for (let i = Math.floor(n/2)-1; i >= 0; i--) heapify(n, i);
  for (let i = n-1; i > 0; i--) { [arr[0], arr[i]] = [arr[i], arr[0]]; heapify(i, 0); }
}

const dups = [3, 1, 4, 1, 5, 9, 2, 6, 5];
heapSort(dups);
console.log(dups);
Output 
[ 1, 1, 2, 3, 4, 5, 5, 6, 9 ]

Notes

| Case | Time | Space | |---------|------------|-------| | Best | O(n log n) | O(1) | | Average | O(n log n) | O(1) | | Worst | O(n log n) | O(1) | Heap sort achieves guaranteed O(n log n) with O(1) auxiliary space, unlike merge sort. However, it is **not stable** and has poor cache performance (heap indexing jumps around memory). In practice quick sort outperforms it on random data. Heap sort is the basis of the selection algorithm that finds the k-th largest element in O(n + k log n).

See also