1. Heap Sort

Heap sort is an in-place comparison-based sorting algorithm that achieves \(O(n \log n)\) in the worst case without requiring auxiliary memory beyond a fixed number of variables. It was introduced by J. W. J. Williams in 1964 ¹². The algorithm works in two phases: first it reorganises the input array into a max-heap data structure, then it repeatedly extracts the maximum element and places it at the end of the array, shrinking the heap by one each time.

Heap sort is the only standard algorithm that combines in-place operation with a strict \(O(n \log n)\) worst-case guarantee — a property that neither quick sort (which is \(O(n^2)\) worst case) nor merge sort (which requires \(O(n)\) auxiliary space) achieves simultaneously. However, its poor cache behaviour relative to quick sort means it is rarely the fastest algorithm in practice.

1.1 Mathematical Foundation

1.1.1 Binary Heap (Array Representation)

A max-heap is a complete binary tree stored in an array \(A[0..n-1]\) (using 0-based indexing) satisfying the heap property:

Parent and child indices in 0-based storage:

1.1.2 MAX-HEAPIFY Cost

Restoring the heap property below node \(i\) in a heap of height \(h\) takes \(O(h)\) comparisons. The height of node \(i\) in a complete binary tree of \(n\) nodes is \(\lfloor \log_2 n \rfloor - \lfloor \log_2(i+1) \rfloor\), so \(O(\log n)\) in the worst case.

1.1.3 BUILD-MAX-HEAP Tight Bound

A naive analysis gives \(O(n \log n)\) for BUILD-MAX-HEAP (calling MAX-HEAPIFY on each of the \(n/2\) interior nodes). The tight bound is \(O(n)\): nodes deep in the tree have small height and cheap heapify calls. Summing:

using \(\sum_{h=0}^{\infty} h/2^h = 2\).

1.2 The Algorithm

MAX-HEAPIFY(A, i, heap-size):
  l = 2i + 1;  r = 2i + 2
  if l < heap-size and A[l] > A[i]: largest = l
  else:                              largest = i
  if r < heap-size and A[r] > A[largest]: largest = r
  if largest ≠ i:
    swap A[i] and A[largest]
    MAX-HEAPIFY(A, largest, heap-size)

BUILD-MAX-HEAP(A, n):
  heap-size = n
  for i = ⌊n/2⌋ - 1 downto 0:   // start from last internal node
    MAX-HEAPIFY(A, i, heap-size)

HEAPSORT(A, n):
  BUILD-MAX-HEAP(A, n)
  for i = n - 1 downto 1:
    swap A[0] and A[i]            // move max to final position
    MAX-HEAPIFY(A, 0, i)          // restore heap on reduced array

1.2.1 Why Start BUILD-MAX-HEAP at \(\lfloor n/2 \rfloor - 1\)?

Nodes with index \(\geq \lfloor n/2 \rfloor\) are leaves and trivially satisfy the heap property (they have no children). Starting heapification at the last non-leaf node \(\lfloor n/2 \rfloor - 1\) and working upward ensures that when MAX-HEAPIFY is called on a node, both its subtrees are already valid heaps.

1.2.2 Correctness: Loop Invariant in HEAPSORT

At the start of each iteration of the for loop with index \(i\):

Sub-array \(A[0..i]\) is a max-heap containing the \(i+1\) smallest elements of the original array; sub-array \(A[i+1..n-1]\) contains the \(n-1-i\) largest elements in sorted order.

Initialisation: after BUILD-MAX-HEAP, \(A[0..n-1]\) is a max-heap (sub-array \(A[i+1..n-1]\) is empty — trivially sorted).
Maintenance: swapping \(A[0]\) (max of heap) to \(A[i]\) extends the sorted suffix; MAX-HEAPIFY restores the heap on \(A[0..i-1]\).
Termination: when \(i = 0\), the sorted suffix spans the entire array.

1.3 Complexity

All three cases (best, average, worst) are \(O(n \log n)\) because every input leads to exactly \(n - 1\) extract-max operations each costing \(O(\log n)\) ¹.

1.4 Properties

1.4.1 In-Place and Not Stable

Heap sort sorts in place (\(O(1)\) auxiliary space beyond the call stack, which is \(O(\log n)\) due to recursive MAX-HEAPIFY). It is not stable: the relative order of equal elements may change because the swap in the main loop can move elements across the sorted/heap boundary.

1.4.2 Cache Behaviour

Heap sort is notoriously cache-unfriendly. MAX-HEAPIFY accesses nodes at indices \(i\), \(2i+1\), \(2i+2\), which in a large array are far apart in memory. By contrast, quick sort and merge sort access elements in more localised patterns, leading to better cache line utilisation and explaining why heap sort is slower in practice despite identical asymptotic complexity.

1.5 Variants

1.5.1 d-ary Heap Sort

Replacing the binary heap with a \(d\)-ary heap reduces the height of the heap to \(\log_d n\), reducing the number of sift-up operations, but increases the number of comparisons per sift-down (d comparisons per level instead of 2). For \(d = 4\), the total number of comparisons is lower in practice and cache behaviour improves slightly due to better branching factor vs. cache line width trade-off.

1.5.2 Min-Heap Variant for Ascending Sort

Alternatively, build a min-heap and extract the minimum each time, placing it at the front. Equivalent in complexity; just reverses the implementation.

1.6 Applications

• Priority queues: the heap data structure extracted from heap sort is used standalone as an efficient priority queue in Dijkstra's algorithm, Prim's algorithm, and event-driven simulation.
• Partial sort / Top-\(k\): to find the top \(k\) elements out of \(n\), build a min-heap of size \(k\) and stream the remaining \(n - k\) elements through it in \(O(n \log k)\) time — far better than full sort when \(k \ll n\).
• Guaranteed worst-case sort: used as the fallback in introsort (C++ std::sort) to prevent quick sort's \(O(n^2)\) degeneration.

1.7 Interactive Demo

The canvas below shows heap sort in two phases: heapify phase (build max-heap, cells colour to show the heap structure) and extract phase (repeat: swap root to end, sift down). Press Play or Step.