FlowLab Logo

Heap Sort Visualizer

SlowFast
520
(7)
69
[0]
12
[1]
87
[2]
98
[3]
89
[4]
72
[5]
24
[6]
Comparing
Swapping
Sorted
Default
Operation Logs
No operations yet
Algorithm Info
Time Complexity: O(n log n) for all cases
Space Complexity: O(1) - in-place sorting
Stable: No - does not maintain relative order of equal elements
How it works: Builds a max heap from the array, then repeatedly extracts the maximum element to get sorted order.
Heapify: Maintains heap property by comparing parent with children and swapping if needed.
Implementation
function heapSort(arr: number[]): number[] {
  const n = arr.length;

  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // Extract elements one by one
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  return arr;
}

function heapify(arr: number[], size: number, root: number) {
  let largest = root;
  const left = 2 * root + 1;
  const right = 2 * root + 2;
  if (left < size && arr[left] > arr[largest]) largest = left;
  if (right < size && arr[right] > arr[largest]) largest = right;
  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, size, largest);
  }
}