JavaScript Program to Implement Heap Sort

This post shows how to implement Heap Sort in JavaScript — a comparison-based sorting algorithm built on top of the binary heap data structure, and a solid way to demonstrate deeper data structure knowledge in interviews.

Heap sort in JavaScript:

Explanation:
Heap sort first builds a "max heap" from the array, where every parent node is larger than its children. The largest element (the root of the heap) is then repeatedly swapped to the end of the array and the heap is "heapified" again to restore its structure, shrinking the heap by one each time. This produces a fully sorted array with guaranteed O(n log n) time complexity.

---

---

JavaScript Program to Implement Heap Sort

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);
  }

  return arr;
}

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

const numbers = [12, 11, 13, 5, 6, 7];
console.log("Sorted array:", heapSort(numbers));

Output:

Sorted array: [ 5, 6, 7, 11, 12, 13 ]

Heap sort is a great way to show you understand both sorting and the heap data structure at once — see more data structure questions in our Interview Prep section, or trace through this code step by step in our Code Runner.

---

Frequently Asked Questions About Heap Sort in JavaScript

What is the time complexity of heap sort?

Heap sort runs in O(n log n) time in the best, average, and worst case, since building the heap takes O(n) and each of the n extraction steps takes O(log n) to re-heapify.

Is heap sort better than quick sort?

Heap sort has a guaranteed O(n log n) worst case, unlike quick sort which can degrade to O(n²). However, quick sort is often faster in practice due to better cache performance and smaller constant factors.

Is heap sort an in-place sorting algorithm?

Yes. Heap sort sorts the array in place using only a constant amount of extra memory, which is an advantage over merge sort's need for additional arrays during merging.