Heaps and Heapsort

Quicksort is fast but has a quadratic worst case; mergesort guarantees $\Theta (n\log n)$ but needs $\Theta (n)$ scratch space. $\text{Heapsort}$ achieves both: a worst-case $\Theta (n\log n)$ bound and sorting in place, using only a constant amount of extra memory. It rests on a data structure, the binary heap, which doubles as an efficient priority queue and so is worth knowing for its own sake well beyond sorting.

The heap as a tree we never build

A (binary) max-heap is a complete binary tree that obeys one local rule.¹

Complete means the tree is filled level by level, top to bottom and left to right, with no gaps until possibly the last level. That rigidity is what lets us discard the tree entirely and store it as a flat array: there is exactly one shape for a complete tree on $n$ nodes, so position in the array is position in the tree.

We store the heap in an array $A[\mathrm{1..}n]$ in level order: the root at $A[1]$, then its two children, then their four children, and so on. With $1$-based indexing the navigation is pure arithmetic, no pointers required:

Doubling an index walks down to a left child; halving walks back up to a parent. On a machine these are single shift operations, which is part of why heaps are fast in practice. Here is a small max-heap shown both as a tree and as the array that actually lives in memory:

Read level by level, the array is

The blue numbers below trace the correspondence: each tree node $i$ lives at array slot $i$, so doubling the index ($2i$, $2i+1$) steps down to a child and halving ($\lfloor i/2\rfloor$) steps back up to the parent.

Check the index rule on $A[2]=14$: its children are at $A[4]=8$ and $A[5]=7$, both smaller, and its parent is at $A[1]=16$, larger. The largest key always sits at the root, $A[1]$. A heap on $n$ nodes is complete, so its height, the number of edges on the longest root-to-leaf path, is $\lfloor {\log }_{2}n\rfloor =\Theta (\log n)$. Every operation below costs at most one such trip up or down the tree.

Two structural facts fall straight out of the indexing and get used constantly. First, node $i$ is a leaf exactly when $\mathrm{left}(i)=2i>n$, that is when $i>\lfloor n/2\rfloor$; so the leaves are precisely $A[\lfloor n/2\rfloor +\mathrm{1..}n]$, and a heap is always at least half leaves ($\lceil n/2\rceil$ of them). Second, the subtree rooted at any node is itself a heap, so every claim we prove about the root applies recursively everywhere.

A heap is not a sorted array: it is far weaker, ordering only along ancestor-descendant paths, with no relation between siblings or cousins. That weakness is what makes a heap cheap to maintain.

Sift-down: restoring the property at one node

The single primitive every heap operation rests on is $\text{Max-Heapify}$. It assumes the subtrees rooted at the two children of $i$ are already max-heaps, but $A[i]$ itself may be smaller than a child and thus violate the property. It repairs the violation by moving $A[i]$ down to its correct level, a motion usually called sift-down.²

We compare $A[i]$ against both children, find the largest of the three, and, if a child wins, swap it up and recurse into the subtree that just received the smaller key. The violation moves strictly down one level each step, so the recursion can run no deeper than the tree is tall: $O(\log n)$ time, $O(1)$ extra space (or $O(\log n)$ stack, trivially made iterative). We track the logical length of the heap in a field $A.heapsize\le A.length$, which lets the array hold heap and non-heap regions side by side, an arrangement central to heapsort below.

A full trace with numbers. Take $A=⟨16,4,10,14,7,9,3,2,8,1⟩$ and call $\text{Max-Heapify}(A,2)$; both subtrees under node $2$ are already heaps, but $A[2]=4$ is smaller than its children.

1. At $i=2$: children are $A[4]=14$ and $A[5]=7$; the largest of $\left\{4,14,7\right\}$ is $14$ at index $4$, so exchange $A[2]\leftrightarrow A[4]$ and recurse on $i=4$.
2. At $i=4$: children are $A[8]=2$ and $A[9]=8$; the largest of $\left\{4,2,8\right\}$ is $8$ at index $9$, so exchange $A[4]\leftrightarrow A[9]$ and recurse on $i=9$.
3. At $i=9$: $\mathrm{left}(9)=18>10=A.heapsize$, so node $9$ is a leaf and the recursion stops.

Two swaps, and the violation is gone. Each swap moved the small key down one level, which is why the total work is bounded by the height.

Building a heap bottom-up

To turn an arbitrary array into a heap we call $\text{Max-Heapify}$ at every internal node, but in the right order. The leaves $A[\lfloor n/2\rfloor +\mathrm{1..}n]$ are already valid one-element heaps, so we start just above them and work upward to the root. Processing a node only after its children are heaps satisfies the precondition $\text{Max-Heapify}$ demands.

On $n=10$ nodes the leaves are $A[\mathrm{6..10}]$ (already heaps, so we skip them), and we sift down the internal nodes $A[5],A[4],\dots ,A[1]$ in that decreasing order, so that every node is processed only after both of its children are.

The loop invariant makes the correctness immediate.

Initialization: nodes $\lfloor n/2\rfloor +\mathrm{1..}n$ are leaves, hence trivial heaps. Maintenance: the children of $i$ are numbered higher than $i$, so by the invariant they head max-heaps, precisely what $\text{Max-Heapify}(A,i)$ needs, and it extends the property to $i$. Termination: when $i=0$, node $1$ (and all others) roots a max-heap.

A full build, step by step

Run $\text{Build-Max-Heap}$ on the unsorted array $A=⟨4,1,3,2,16,9,10,14,8,7⟩$, with $n=10$ and first internal node $\lfloor 10/2\rfloor =5$.

• $i=5$: $A[5]=16$ has one child, $A[10]=7$. Already the larger; no swap.
• $i=4$: $A[4]=2$ versus children $A[8]=14$, $A[9]=8$. Swap with $14$; the recursion hits a leaf and stops.
• $i=3$: $A[3]=3$ versus $A[6]=9$, $A[7]=10$. Swap with $10$; leaf, stop.
• $i=2$: $A[2]=1$ versus $A[4]=14$, $A[5]=16$. Swap with $16$; then at node $5$, $1<7=A[10]$, so swap again; leaf, stop. The key $1$ sank two levels.
• $i=1$: $A[1]=4$ versus $16$ and $10$. Swap with $16$; at node $2$, $4$ versus $14,7$: swap with $14$; at node $4$, $4$ versus $2,8$: swap with $8$; leaf, stop. Three levels, the full height.

The result reproduces the heap from the start of the lesson, $⟨16,14,10,8,7,9,3,2,4,1⟩$. Late iterations do more work per call, but there are geometrically fewer of them; the next section shows the total is linear.

Why it is $O(n)$, not $O(n\log n)$

The easy bound is immediate: there are $O(n)$ calls to $\text{Max-Heapify}$, each costing $O(\log n)$, for $O(n\log n)$. That is correct but loose, and the looseness matters. Most nodes are near the bottom of the tree, where $\text{Max-Heapify}$ has almost nothing to do.

A heap of $n$ nodes has at most $\lceil n/2^{h+1}\rceil$ nodes at height $h$, and a sift-down from height $h$ costs $O(h)$. Summing the real work over all heights,

The series ${\sum }_{h\ge 0}h/2^h$ converges to $2$, using the standard identity ${\sum }_{h\ge 0}h{x}^h=x/(1-x{)}^2$ at $x=\frac{1}{2}$. The infinite sum is a constant, so the whole bound collapses to $O(n)$.

The intuition behind the algebra: half the nodes are leaves (zero work), a quarter sit one level up (at most one swap each), an eighth two levels up, and so on. Cost per node falls geometrically as the number of nodes at that level rises geometrically, and the two effects cancel to leave a linear total.³ Building a heap is asymptotically negligible compared to the sort that follows.

Heapsort

A max-heap keeps the largest element at the root, $A[1]$. To sort, we repeatedly move that maximum to where it belongs, the back of the array, then shrink the heap and repair it.

The array splits into two regions: a heap at the front, $A[\mathrm{1..}A.heapsize]$, and a growing sorted suffix at the back. Each iteration swaps the heap's maximum into the slot just before the sorted suffix, drops the heap size by one, and runs a single sift-down from the root to re-establish the max-heap property on the smaller heap. After $n-1$ iterations the heap is a single element, necessarily the global minimum, and $A$ is sorted ascending.

The invariant holds initially because $\text{Build-Max-Heap}$ makes all of $A[\mathrm{1..}n]$ a heap and the suffix is empty. Each iteration maintains it: $A[1]$ is the maximum of the heap region, hence no larger than anything already in the suffix and no smaller than anything left in the heap, so swapping it into the slot just before the suffix extends the sorted region by one correct element; shrinking the heap and sifting the displaced key down restores the heap half of the invariant. At termination the heap region is the single smallest element sitting in $A[1]$, so the whole array is sorted.

Watching the first few extractions on our running heap $⟨16,14,10,8,7,9,3,2,4,1⟩$ makes the two-region structure visible:

Row by row: swapping $16$ with the last leaf $1$ puts $1$ at the root, and the sift-down walks it back to the bottom ($1<14$, then $1<8$, then $1<4$), producing $⟨14,8,10,4,7,9,3,2,1⟩$; the next extraction swaps $14$ with $1$ and sifts again. Every extraction pays one root-to-leaf trip, $O(\log n)$, and there is no lucky input: after the swap the root holds a key that came from a leaf, almost always small, so the sift-down nearly always runs the full height.

auxiliary space beyond the array) but not stable: the swaps scatter equal keys. Compared to its peers it lacks quicksort's cache-friendliness, since the parent/child jumps roam across memory, which is why quicksort usually wins in practice despite the worse worst case. Heapsort's niche is the guaranteed $\Theta (n\log n)$ ceiling with no extra memory, exactly the property introsort borrows as a fallback when quicksort's recursion runs too deep.⁴

from typing import TypeVar

from comparable import Comparable

# the elements must support ordering; any total order works.
Element = TypeVar("Element", bound=Comparable)

def _sift_down(heap: list[Element], position: int, heap_size: int) -> None:
  """
    Max-Heapify on `heap[0..heap_size)`: float the key at `position` down.\n
    Children of `position` are at 2*position+1 and 2*position+2; only the\n
    region below `heap_size` counts as the heap, leaving the sorted suffix\n
    (at or above `heap_size`) untouched.\n
  """
  while True:

    # pick the largest among the node and its two in-heap children.
    largest: int = position
    left: int = 2 * position + 1
    right: int = 2 * position + 2
    if left < heap_size and heap[left] > heap[largest]:
      largest = left
    if right < heap_size and heap[right] > heap[largest]:
      largest = right

    # settled once the node already dominates its children.
    if largest == position:
      return

    # swap the bigger child up and keep sinking into the disturbed child.
    heap[position], heap[largest] = heap[largest], heap[position]
    position = largest

def _build_max_heap(heap: list[Element]) -> None:
  """
    Turn `heap` into a max-heap bottom-up in O(n).\n
    Sift down each internal node in decreasing index, so every node is\n
    processed only after both of its children are already heaps.\n
  """
  size: int = len(heap)
  last_internal: int = size // 2 - 1
  for position in range(last_internal, -1, -1):
    _sift_down(heap, position, size)

def heapsort(data: list[Element]) -> list[Element]:
  """
    Return a new list holding `data` sorted ascending, via heapsort.\n
    Runs in Theta(n log n) in best, average, and worst case.\n
  """
  heap: list[Element] = list(data)
  heapsort_in_place(heap)
  return heap

def heapsort_in_place(heap: list[Element]) -> None:
  """
    Sort `heap` ascending in place using the array itself as the heap.\n
    Uses only O(1) auxiliary space beyond the input list.\n
  """
  # heapify, then repeatedly extract the max into the growing sorted suffix.
  _build_max_heap(heap)
  for last in range(len(heap) - 1, 0, -1):

    # the current maximum (root) goes to its final slot at the suffix front.
    heap[0], heap[last] = heap[last], heap[0]

    # the heap shrinks to exclude that slot; repair the new root.
    _sift_down(heap, 0, last)

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

Heapsort in practice

Asymptotically, heapsort ties mergesort and beats quicksort's worst case. Measured on real machines it is slower, for several reasons.⁵

• Cache behavior. Quicksort's partition scans memory left to right, so nearly every access hits a cache line already loaded. Heapsort's inner loop jumps from index $i$ to $2i$, doubling its stride every level; once the heap outgrows the cache, most sift-down steps are cache misses. Same $\Theta (n\log n)$ comparison count, very different memory-access cost.
• Comparisons per element. Each sift-down at height $h$ makes up to $2h$ comparisons (find the larger child, then compare it to the sinking key), so heapsort's constant is roughly $2n{\log }_{2}n$ against quicksort's average $\approx 1.39n{\log }_{2}n$.
• Small inputs. For $n$ below a few dozen, simple insertion sort beats every $\Theta (n\log n)$ method: its constants are tiny, it is stable, and on nearly-sorted data it approaches linear time. Production sorts therefore cut over to insertion sort on small subproblems rather than recursing or heapifying to the bottom.

These forces meet in introsort, the algorithm behind most C++ standard library sort implementations: run quicksort for its cache behavior and low constants, switch any subproblem smaller than a fixed threshold to insertion sort, and, if the recursion depth ever exceeds about $2{\log }_{2}n$ (the sign of a degenerate pivot sequence), abandon quicksort for heapsort on that subproblem. Heapsort is rarely executed there, but it converts quicksort's $\Theta (n^2)$ worst case into a hard $\Theta (n\log n)$ ceiling with no extra memory. Where heapsort wins outright is partial sorting: to get the $k$ largest of $n$ elements, build a heap in $O(n)$ and extract $k$ times, for $O(n+k\log n)$, far cheaper than sorting everything when $k\ll n$.

Priority queues

Sorting is only the first use of a heap. The same structure implements a priority queue: a set $S$ of elements, each with a key (its priority), supporting

• $\text{Insert}(S,x)$: add $x$ to $S$;
• $\text{Maximum}(S)$: return the element with the largest key;
• $\text{Extract-Max}(S)$: remove and return that element;
• $\text{Increase-Key}(S,x,k)$: raise $x$'s key to $k$.

A max-heap answers Maximum in $O(1)$, since it is just $A[1]$, and supports the mutating operations in $O(\log n)$, the height of the tree.⁵

$\text{Increase-Key}$ moves the other direction: bump a key and sift up, repeatedly swapping with the parent while the heap property is violated, again in $O(\log n)$. Insert is just an $\text{Increase-Key}$ from $-\infty$: append the new element as the last leaf, then sift it up.

Sift-up is cheaper than sift-down per level, one comparison against the parent instead of two against children, and it touches only the ancestors of $i$, a single path of length at most $\lfloor {\log }_{2}n\rfloor$. The correctness argument mirrors sift-down's: the only edge that can violate the heap property is the one between the raised key and its parent, the swap moves the violation up one level, and it disappears at the root.

Viewed this way, heapsort is $n$ successive $\text{Extract-Max}$ operations, writing each maximum into the vacancy the shrinking heap leaves behind. Priority queues built this way drive Dijkstra's shortest paths, Prim's minimum spanning tree, event-driven simulation, and any scheduler that must repeatedly serve the most urgent task.

from collections.abc import Iterable
from typing import Generic, TypeVar

from comparable import Comparable

# the keys must support ordering; any total order works (numbers, tuples, …).
Key = TypeVar("Key", bound=Comparable)

def _parent(position: int) -> int:
  """
    Index of the parent of the node at `position` (0-based heap).\n
  """
  return (position - 1) // 2

def _left(position: int) -> int:
  """
    Index of the left child of the node at `position`.\n
  """
  return 2 * position + 1

def _right(position: int) -> int:
  """
    Index of the right child of the node at `position`.\n
  """
  return 2 * position + 2

class MaxHeap(Generic[Key]):
  """
    A max-heap / max-priority-queue over comparable keys.\n
    The largest key always sits at the root. The heap obeys the max-heap\n
    property: every node's key is at least each of its children's keys.\n
  """

  def __init__(self, keys: Iterable[Key] | None = None) -> None:
    """
      Build a heap from `keys` in O(n) via bottom-up sift-down, or start\n
      empty when `keys` is None.\n
    """
    self._heap: list[Key] = list(keys) if keys is not None else []
    self._build()

  def __len__(self) -> int:
    return len(self._heap)

  def __bool__(self) -> bool:
    return bool(self._heap)

  def __contains__(self, key: Key) -> bool:
    return key in self._heap

  def _build(self) -> None:
    """
      Turn the underlying array into a max-heap bottom-up.\n
      Leaves are trivial heaps, so we sift down only the internal nodes,\n
      in decreasing index, each after its children are already heaps.\n
    """
    size: int = len(self._heap)
    last_internal: int = size // 2 - 1
    for position in range(last_internal, -1, -1):
      self._sift_down(position)

  def _sift_down(self, position: int) -> None:
    """
      Max-Heapify: float the key at `position` down to its rightful level.\n
      Assumes both child subtrees already satisfy the max-heap property.\n
    """
    size: int = len(self._heap)
    while True:

      # pick the largest among the node and its two children.
      largest: int = position
      left: int = _left(position)
      right: int = _right(position)
      if left < size and self._heap[left] > self._heap[largest]:
        largest = left
      if right < size and self._heap[right] > self._heap[largest]:
        largest = right

      # settled once the node already dominates its children.
      if largest == position:
        return

      # the bigger child moves up; continue sinking into the disturbed child.
      self._heap[position], self._heap[largest] = (
        self._heap[largest],
        self._heap[position],
      )
      position = largest

  def _sift_up(self, position: int) -> None:
    """
      Float the key at `position` up while it exceeds its parent.\n
      The mirror of sift-down, used by insert and increase-key.\n
    """
    while position > 0:

      # stop once the parent already dominates this key.
      parent: int = _parent(position)
      if self._heap[position] <= self._heap[parent]:
        return

      # swap past the parent and keep rising from its slot.
      self._heap[position], self._heap[parent] = (
        self._heap[parent],
        self._heap[position],
      )
      position = parent

  def maximum(self) -> Key:
    """
      The largest key, in O(1) — the root. Raises if the heap is empty.\n
    """
    if not self._heap:
      raise IndexError("maximum from an empty heap")
    return self._heap[0]

  def insert(self, key: Key) -> None:
    """
      Add `key` to the heap in O(log n): append as the last leaf, sift up.\n
    """
    self._heap.append(key)
    self._sift_up(len(self._heap) - 1)

  def extract_max(self) -> Key:
    """
      Remove and return the largest key in O(log n).\n
      Move the last leaf to the root, shrink, then sift the new root down.\n
    """
    if not self._heap:
      raise IndexError("extract_max from an empty heap")

    # remember the root, then pop the last leaf off the tail.
    largest: Key = self._heap[0]
    last: Key = self._heap.pop()

    # promote that leaf to the root and sink it to repair the heap.
    if self._heap:
      self._heap[0] = last
      self._sift_down(0)

    return largest

  def increase_key(self, position: int, key: Key) -> None:
    """
      Raise the key at `position` to `key`, then sift up to restore order.\n
      Raises ValueError if `key` is smaller than the current key there.\n
    """
    if position < 0 or position >= len(self._heap):
      raise IndexError("increase_key position out of range")
    if key < self._heap[position]:
      raise ValueError("new key is smaller than the current key")

    # raise the key in place, then float it up to its new level.
    self._heap[position] = key
    self._sift_up(position)

  def is_heap(self) -> bool:
    """
      Whether the array currently satisfies the max-heap property.\n
      A linear self-check, handy for tests and invariant assertions.\n
    """
    size: int = len(self._heap)

    # any in-range child that outranks its parent breaks the property.
    for position in range(size):
      left: int = _left(position)
      right: int = _right(position)
      if left < size and self._heap[left] > self._heap[position]:
        return False
      if right < size and self._heap[right] > self._heap[position]:
        return False

    return True

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

Priority queue variants

The binary heap is the baseline priority queue; several variants trade its simple array layout for better bounds on particular operations, and the right choice depends on which operation dominates.

$d$-ary heaps. Give each node $d$ children instead of $2$ and the tree gets shallower, height ${\log }_{d}n$, so sift-up (one comparison per level) speeds up to $O({\log }_{d}n)$. Sift-down gets slower per level, though — it must find the largest of $d$ children, $d-1$ comparisons — so the trade favors $d>2$ exactly when insertions and key-decreases outnumber extractions. That is precisely Dijkstra's and Prim's access pattern on dense graphs, where a $4$-ary heap measurably beats a binary one. The array layout and index arithmetic generalize directly: child $j$ of node $i$ sits at $di-d+2+j$.

Fibonacci and pairing heaps. The binary heap does every mutating operation in $\Theta (\log n)$. For graph algorithms the bottleneck operation is $\text{Decrease-Key}$, called once per edge, and the Fibonacci heap (Fredman and Tarjan, 1984) drives its amortized cost to $O(1)$, with $\text{Extract-Min}$ staying $O(\log n)$ amortized. Plugging it into Dijkstra improves the bound from $O(E\log V)$ to $O(E+V\log V)$ — asymptotically the best known for the comparison model. The catch is a large constant and a tangle of lazy trees and cut marks that make it slow in practice; the simpler pairing heap (Fredman et al., 1986) achieves nearly the same bounds with far less bookkeeping and usually wins on real inputs. These are the standard illustration that amortized and worst-case-per-operation are different design targets.

Cache-aware layouts. As with heapsort itself, the binary heap's index-doubling roams across memory and misses cache once it outgrows the L2. Layouts that reduce this — B-heaps (arranging the tree so each cache-line-sized block holds a subtree) and the array-backed $d$-ary heaps above — keep more of each sift-down within one cache line. The same principle appears in external sorting and B-trees: on real memory hierarchies the branching factor is tuned to the block, not left at $2$.⁵

Takeaways

• A binary heap is a complete binary tree stored as an array; index arithmetic ($\mathrm{parent}(i)=\lfloor i/2\rfloor$, children $2i$ and $2i+1$) replaces pointers, and the height is $\Theta (\log n)$.
• The max-heap property orders only ancestor over descendant: weak enough to maintain cheaply, strong enough to keep the maximum at the root.
• $\text{Max-Heapify}$ (sift-down) repairs one violation in $O(\log n)$; $\text{Build-Max-Heap}$ applies it bottom-up in $O(n)$, since work falls geometrically while node counts rise geometrically.
• $\text{Heapsort}$ repeatedly extracts the max into the array's tail, sorting in place in $\Theta (n\log n)$ in all cases, though it is unstable and not cache-friendly.
• In practice it loses to quicksort on caches and constants; its niches are introsort's worst-case fallback, small-$n$ cutoffs aside, and $O(n+k\log n)$ partial sorting for the top $k$.
• The same heap is a priority queue: $O(1)$ maximum, $O(\log n)$ insert, extract-max, and increase-key, the operations Dijkstra, Prim, and schedulers are built on.