Heap Sort Algorithm

The heap sort algorithm turns the list into a max-heap, then repeatedly moves the largest element to the end and repairs the heap. It guarantees O(n log n) time with only O(1) extra memory. Step through it below, then read how it works.

What is Heap Sort?

Heap Sort first rearranges the list into a max-heap, a binary tree stored in the array in which every parent is at least as large as its children. It then repeatedly swaps the root (the largest value) with the last unsorted element and restores the heap.

Key insight: In an array-based heap, the children of position i are at 2i + 1 and 2i + 2. The largest element is always at position 0, so extracting it repeatedly produces the list in sorted order from the back.

Heap Sort Time Complexity

Measure	Value
Best case	O(n log n)
Average case	O(n log n)
Worst case	O(n log n)
Space	O(1)
Stable	No

For a formal definition and complexity analysis, see the NIST Dictionary of Algorithms and Data Structures entry for heapsort.

Algorithm Steps

1. Build a max-heap from the list, starting at the last parent and sifting each node down.
2. Swap the root (largest) with the last element of the heap.
3. Reduce the heap size by one; the swapped element is now in its final place.
4. Sift the new root down to restore the max-heap.
5. Repeat until the heap has one element.

Advantages and Disadvantages

Advantages

• Guaranteed O(n log n) in all cases
• In place with O(1) extra memory
• No worst-case slowdown like Quick Sort

Disadvantages

• Not stable
• Slower in practice than Quick Sort because of poor cache locality
• More complex to implement than the basic sorts

Real-World Applications

• Systems that need guaranteed O(n log n) time and O(1) extra memory
• Real-time and embedded systems where worst-case behaviour matters
• Priority queues and scheduling (the heap data structure itself)
• Fallback in introsort when Quick Sort recursion becomes too deep

When to Use Heap Sort

Choose it when you need a worst-case guarantee and cannot afford extra memory. It is also the right mental model for priority queues.

Heap Sort Implementation

Python

def heapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):   # build max-heap
        heapify(arr, n, i)
    for end in range(n - 1, 0, -1):       # extract maximum
        arr[0], arr[end] = arr[end], arr[0]
        heapify(arr, end, 0)
    return arr

JavaScript

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1, 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);
  }
}

function heapSort(arr) {
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i); // build max-heap
  for (let end = n - 1; end > 0; end--) {                             // extract maximum
    [arr[0], arr[end]] = [arr[end], arr[0]];
    heapify(arr, end, 0);
  }
  return arr;
}

FAQ

What is a max-heap?

A complete binary tree, stored in an array, where every parent is at least as large as its children. The element at index i has its children at 2i + 1 and 2i + 2, so no pointers are needed and the largest value is always at index 0.

Is heap sort stable?

No. Swapping the root with the last element and sifting down moves elements over long distances, so equal values can swap order.

If heap sort is O(n log n) in every case, why is quick sort used more?

Heap sort jumps around the array between parents and children, which is unfriendly to CPU caches, so Quick Sort is usually faster in practice. Heap sort is valued as a safety net: introsort switches to it when quick sort recurses too deeply.

---

More Sorting Algorithms

• Quick Sort
• Merge Sort
• Selection Sort
• Timsort