Heap Sort

Overview

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It builds a max heap (for ascending order) from the input array and repeatedly extracts the maximum element from the heap, placing it at the end of the sorted portion of the array.

Heap Sort provides guaranteed O(n log n) time complexity in all cases while using only O(1) extra space, making it an excellent choice when you need in-place sorting with predictable performance.

How It Works

The algorithm follows these steps:

  1. Build Max Heap: Convert the array into a max heap structure
  2. Extract Maximum: Swap the root (maximum element) with the last element
  3. Heapify: Restore the heap property for the reduced heap
  4. Repeat: Continue until the heap is empty

A max heap is a complete binary tree where each parent node is greater than or equal to its children. This property ensures the maximum element is always at the root.

Algorithm


HeapSort(arr):
    n = length of arr
    
    # Build max heap
    for i = n/2 - 1 down to 0:
        Heapify(arr, n, i)
    
    # Extract elements from heap one by one
    for i = n - 1 down to 1:
        swap arr[0] and arr[i]  # Move root to end
        Heapify(arr, i, 0)      # Heapify reduced heap

Heapify(arr, n, i):
    largest = i
    left = 2*i + 1
    right = 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:
        swap arr[i] and arr[largest]
        Heapify(arr, n, largest)

Implementation


def heap_sort(arr):
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements from heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # Move root to end
        heapify(arr, i, 0)  # Heapify reduced heap
    
    return arr

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 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)

Complexity Analysis

  • Time Complexity: O(n log n) in all cases (best, average, and worst)
    • Building the heap: O(n)
    • Extracting n elements: O(n log n)
    • Total: O(n log n)
  • Space Complexity: O(log n) as written below, because heapify recurses to a depth equal to the tree height. Rewriting the sift-down as an iterative loop (shown below) makes it genuinely O(1), which is heap sort's main selling point.
def heapify_iterative(arr, n, i):
    """Sift-down without recursion - true O(1) auxiliary space."""
    while True:
        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:
            return
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

Unlike Quick Sort, Heap Sort guarantees O(n log n) regardless of input, which makes it predictable. Note that building the heap is O(n), not O(n log n) — a frequently misquoted result. Most nodes sit near the bottom of the tree and sift down only a short distance; summing height×count over all levels telescopes to O(n).

So why is heap sort not the default sort anywhere? Cache behaviour. Sift-down jumps between indices i, 2i+1, 4i+3 and so on, which scatters accesses across memory and misses cache constantly. Quicksort scans linearly and, despite its O(n²) worst case, typically runs two to three times faster on real hardware. Heap sort's practical role today is as the safety net inside introsort: quicksort runs, and if recursion gets too deep, the implementation switches to heap sort to guarantee the O(n log n) bound.

Characteristics

  • Stable: No - does not preserve relative order of equal elements
  • In-place: Yes - only requires O(1) extra space
  • Adaptive: No - always performs the same operations
  • Online: No - requires the entire array to be present

When to Use Heap Sort

Heap Sort is an excellent choice when:

  • You need guaranteed O(n log n) performance and cannot tolerate worst-case O(n²)
  • In-place sorting is required with minimal space overhead
  • You need a predictable, consistent sorting algorithm
  • Worst-case performance is more important than average-case optimization
  • You're already working with heap data structures

Understanding the Heap Structure

In a max heap represented as an array:

  • Parent at index i has children at indices 2i+1 and 2i+2
  • Child at index i has parent at index (i-1)/2
  • The root (maximum element) is at index 0
  • The heap property: arr[parent] >= arr[child] for all nodes

Example

Sorting [12, 11, 13, 5, 6, 7]: 

Build max heap:
        12
      /    \
    11      13
   /  \    /
  5    6  7

After heapify:
        13
      /    \
    11      12
   /  \    /
  5    6  7

Extract and sort:
Step 1: Swap 13 and 7, heapify
Step 2: Swap 12 and 6, heapify
Step 3: Swap 11 and 5, heapify
...
Final: [5, 6, 7, 11, 12, 13]

Related Algorithms

Explore other sorting algorithms: