Heap Sort

Tags

Heap Sort

Category

Sorting

Difficulty

Hard

Problem Statement

Implement the heap sort algorithm to sort an array of integers in ascending order. Heap sort leverages a binary heap data structure to efficiently extract elements in sorted order.

Intuition

A max-heap guarantees that the largest element is always at the root. By building a max-heap from the input array, we can repeatedly extract the maximum element and place it at the end of the array. After each extraction, we restore the heap property on the reduced heap. This produces a sorted array in ascending order.

Approach

  1. Build a max-heap from the input array by calling sift-down on every non-leaf node, starting from the last non-leaf and working up to the root.
  2. Extract elements one at a time:
    • Swap the root (maximum) with the last element of the heap.
    • Reduce the heap size by one.
    • Sift down the new root to restore the max-heap property.
  3. Repeat until the heap size is 1.

Pseudocode

function heapSort(array):
    // Build max-heap
    lastParent = (length(array) - 2) / 2   // integer division
    for i from lastParent down to 0:
        siftDown(array, i, length(array) - 1)

    // Extract elements
    for endIdx from length(array) - 1 down to 1:
        swap(array[0], array[endIdx])
        siftDown(array, 0, endIdx - 1)
    return array

function siftDown(array, currentIdx, endIdx):
    childOneIdx = 2 * currentIdx + 1
    while childOneIdx <= endIdx:
        childTwoIdx = 2 * currentIdx + 2 if 2 * currentIdx + 2 <= endIdx else -1
        if childTwoIdx != -1 and array[childTwoIdx] > array[childOneIdx]:
            idxToSwap = childTwoIdx
        else:
            idxToSwap = childOneIdx
        if array[idxToSwap] > array[currentIdx]:
            swap(array[currentIdx], array[idxToSwap])
            currentIdx = idxToSwap
            childOneIdx = 2 * currentIdx + 1
        else:
            break

Time & Space Complexity

  • Time: O(n log n) in all cases (best, average, worst). Building the heap is O(n). Each of the n extractions requires O(log n) sift-down operations.
  • Space: O(1) — Sorting is done entirely in-place. No auxiliary array or recursion stack is needed (sift-down is iterative).

Key Insights

  • Heap sort has guaranteed O(n log n) worst-case time, unlike quick sort.
  • Building the heap via sift-down is O(n), not O(n log n), because most nodes are near the bottom and require few sift operations.
  • Heap sort is not stable — the extraction step changes the relative order of equal elements.
  • It has poor cache performance compared to quick sort because it accesses memory in a non-sequential pattern (parent-child jumps).
  • O(1) space makes heap sort ideal when memory is constrained.

Edge Cases

  • Empty array — nothing to sort.
  • Single-element array — already sorted.
  • Already sorted array — still O(n log n); the heap build rearranges elements.
  • All identical elements — sift-down terminates immediately at each step, but overall still O(n log n) comparisons.
  • Two elements — one comparison and at most one swap.

Linked mentions