Mastering Algorithms

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(1) - only uses a constant amount of extra space (in-place)

Unlike Quick Sort, Heap Sort guarantees O(n log n) performance regardless of input distribution, making it more predictable.

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: