---
title: Heaps and Heapsort
module: Sorting & Order Statistics
moduleNumber: 3
lessonNumber: 1
order: 301
summary: |
  A binary heap is a tree we store flat in an array, with index arithmetic
  standing in for pointers. We build the max-heap property bottom-up in $O(n)$
  time, sort in place in $\Theta(n\log n)$ by repeatedly extracting the maximum,
  and reuse the same structure to implement a priority queue.
topics: [Heaps, Comparison Sorting]
sources:
  - book: CLRS
    ref: "Ch. 6 — Heapsort"
  - book: Skiena
    ref: "§4.3, §12.2 — Heaps and Priority Queues"
  - book: Erickson
    ref: "Ch. — Data Structures"
practice:
  - title: 'Last Stone Weight'
    slug: last-stone-weight
    difficulty: Easy
  - title: 'Kth Largest Element in a Stream'
    slug: kth-largest-element-in-a-stream
    difficulty: Easy
  - title: 'Top K Frequent Elements'
    slug: top-k-frequent-elements
    difficulty: Medium
  - title: 'Merge k Sorted Lists'
    slug: merge-k-sorted-lists
    difficulty: Hard
  - title: 'Find Median from Data Stream'
    slug: find-median-from-data-stream
    difficulty: Hard
---

[Quicksort](/algorithms/divide-and-conquer/quicksort) is fast but has a quadratic worst case; [mergesort](/algorithms/divide-and-conquer/mergesort) guarantees
$\Theta(n\log n)$ but needs $\Theta(n)$ scratch space. $\textsc{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.[^clrs-heap]

> **Property (Max-heap).** Every node's key is at least the key of each of its
> children. Equivalently, the key of any node is $\ge$ the keys of all its
> descendants.

"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[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:

$$
\parent(i) = \floor{i/2}, \qquad
\operatorname{left}(i) = 2i, \qquad
\operatorname{right}(i) = 2i + 1.
$$

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:

$$
% caption: A small max-heap drawn as a binary tree.
\begin{tikzpicture}[level distance=12mm,
  level 1/.style={sibling distance=34mm},
  level 2/.style={sibling distance=17mm},
  every node/.style={draw, circle, minimum size=8mm, font=\small}]
  \node {16}
    child {node {14}
      child {node {8}
        child {node {2}}
        child {node {4}}}
      child {node {7}
        child {node {1}}}}
    child {node {10}
      child {node {9}}
      child {node {3}}};
\end{tikzpicture}
$$

Read level by level, the array is

$$
A = \vector{16,\ 14,\ 10,\ 8,\ 7,\ 9,\ 3,\ 2,\ 4,\ 1}.
$$

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 ($\floor{i/2}$) steps back up to the parent.

$$
% caption: The same heap as tree and array: node $i$ sits at array slot $i$, with children
%          at $2i$ and $2i+1$. Doubling an index steps down a level; halving steps up.
\begin{tikzpicture}[
  n/.style={circle, draw, minimum size=7mm, font=\small, inner sep=0pt},
  cell/.style={draw, minimum size=7mm, font=\small, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[n] (a1) at (0,0) {16};
  \node[n] (a2) at (-2.0,-1.2) {14};
  \node[n] (a3) at (2.0,-1.2) {10};
  \node[n] (a4) at (-3.0,-2.4) {8};
  \node[n] (a5) at (-1.0,-2.4) {7};
  \node[n] (a6) at (1.0,-2.4) {9};
  \node[n] (a7) at (3.0,-2.4) {3};
  \draw (a1)--(a2); \draw (a1)--(a3);
  \draw (a2)--(a4); \draw (a2)--(a5);
  \draw (a3)--(a6); \draw (a3)--(a7);
  \node[font=\scriptsize, text=acc] at (0,0.55) {1};
  \node[font=\scriptsize, text=acc] at (-2.0,-0.65) {2};
  \node[font=\scriptsize, text=acc] at (2.0,-0.65) {3};
  \node[font=\scriptsize, text=acc] at (-3.0,-1.85) {4};
  \node[font=\scriptsize, text=acc] at (-1.0,-1.85) {5};
  \node[font=\scriptsize, text=acc] at (1.0,-1.85) {6};
  \node[font=\scriptsize, text=acc] at (3.0,-1.85) {7};
  \foreach \v/\i in {16/1,14/2,10/3,8/4,7/5,9/6,3/7}
    \node[cell] (c\i) at (\i*0.8-0.4,-4.0) {\v};
  \foreach \i in {1,...,7}
    \node[font=\scriptsize, text=acc] at (\i*0.8-0.4,-4.55) {\i};
  \node[font=\footnotesize, anchor=east] at (-0.1,-4.0) {$A$};
\end{tikzpicture}
$$

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
$\floor{\log_2 n} = \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 $\operatorname{left}(i) = 2i > n$,
that is when $i > \floor{n/2}$; so the leaves are precisely
$A[\floor{n/2}+1 .. n]$, and a heap is always at least half leaves
($\ceil{n/2}$ 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 $\textsc{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**.[^erickson-ds]

```algorithm
caption: $\textsc{Max-Heapify}(A, i)$ — sift $A[i]$ down to restore the heap property
number: 1
$\ell \gets \operatorname{left}(i)$
$r \gets \operatorname{right}(i)$
if $\ell \le A.heapsize$ and $A[\ell] > A[i]$ then
  $largest \gets \ell$
else
  $largest \gets i$
if $r \le A.heapsize$ and $A[r] > A[largest]$ then
  $largest \gets r$
if $largest \ne i$ then
  exchange $A[i]$ with $A[largest]$ // bigger child moves up
  call $\textsc{Max-Heapify}(A, largest)$ // fix the disturbed subtree
```

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.

$$
% caption: Max-Heapify with both subtrees already valid heaps: the small root key sinks
%          along its path, swapping with the larger child at each step.
\begin{tikzpicture}[n/.style={circle, draw, minimum size=7.5mm, font=\small, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[n, fill=red!18] (r) at (0,0) {4};
  \node[n, fill=acc!12] (l) at (-1.7,-1.3) {14};
  \node[n] (rt) at (1.7,-1.3) {10};
  \node[n, fill=acc!12] (ll) at (-2.6,-2.7) {8};
  \node[n] (lr) at (-0.8,-2.7) {7};
  \node[n] (rl) at (0.8,-2.7) {9};
  \node[n] (rr) at (2.6,-2.7) {3};
  \draw (r)--(l); \draw (r)--(rt); \draw (l)--(ll); \draw (l)--(lr); \draw (rt)--(rl); \draw (rt)--(rr);
  \draw[<->, red, thick] (r) to[bend right=18] node[left,font=\scriptsize] {swap 1} (l);
  \draw[<->, red, thick] (l) to[bend right=18] node[left,font=\scriptsize] {swap 2} (ll);
\end{tikzpicture}
$$

> **Correctness.** When $\textsc{Max-Heapify}(A,i)$ is called with both child
> subtrees being valid max-heaps, it leaves the subtree rooted at $i$ a valid
> max-heap. _Proof sketch:_ the largest of $\set{A[i], A[\ell], A[r]}$ is placed
> at $i$, dominating both children; the only subtree possibly disturbed is the
> one the old root sank into, and the recursive call fixes it. The recursion
> terminates because the index strictly increases (we move to a child) and is
> bounded by $n$.

A full trace with numbers. Take $A = \vector{16, 4, 10, 14, 7, 9, 3, 2, 8, 1}$
and call $\textsc{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
   $\set{4, 14, 7}$ 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
   $\set{4, 2, 8}$ is $8$ at index $9$, so exchange $A[4] \leftrightarrow A[9]$
   and recurse on $i = 9$.
3. **At $i=9$:** $\operatorname{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.

$$
% caption: The same trace at array level: $\textsc{Max-Heapify}(A,2)$ on
%          $A=\langle 16,4,10,14,7,9,3,2,8,1\rangle$. The key $4$ (red) swaps with the
%          larger child $14$ (slot $2$ with slot $4$), then with the larger child $8$
%          (slot $4$ with slot $9$), then stops at a leaf.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=7mm, font=\small, inner sep=0pt},
  lbl/.style={font=\footnotesize, anchor=east}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i in {1,...,10} \node[font=\scriptsize, text=black] at (\i*0.75,0.62) {\i};
  \node[lbl] at (0.2,0) {start};
  \foreach \v/\i in {16/1,10/3,14/4,7/5,9/6,3/7,2/8,8/9,1/10} \node[cell] at (\i*0.75,0) {\v};
  \node[cell, fill=red!16] at (2*0.75,0) {4};
  \node[lbl] at (0.2,-1.1) {swap 2, 4};
  \foreach \v/\i in {16/1,10/3,7/5,9/6,3/7,2/8,8/9,1/10} \node[cell] at (\i*0.75,-1.1) {\v};
  \node[cell, fill=red!16] at (4*0.75,-1.1) {4};
  \node[cell, fill=acc!14] at (2*0.75,-1.1) {14};
  \node[lbl] at (0.2,-2.2) {swap 4, 9};
  \foreach \v/\i in {16/1,14/2,10/3,7/5,9/6,3/7,2/8,1/10} \node[cell] at (\i*0.75,-2.2) {\v};
  \node[cell, fill=red!16] at (9*0.75,-2.2) {4};
  \node[cell, fill=acc!14] at (4*0.75,-2.2) {8};
  \node[font=\footnotesize, text=black, anchor=west] at (8.15,-2.2) {leaf: stop};
\end{tikzpicture}
$$

## Building a heap bottom-up

To turn an arbitrary array into a heap we call $\textsc{Max-Heapify}$ at every internal
node, but in the right order. The leaves $A[\floor{n/2}+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 $\textsc{Max-Heapify}$ demands.

```algorithm
caption: $\textsc{Build-Max-Heap}(A)$ — turn $A[1..n]$ into a max-heap
number: 2
$A.heapsize \gets A.length$
for $i \gets \floor{A.length / 2}$ downto $1$ do
  call $\textsc{Max-Heapify}(A, i)$ // children already heaps
```

On $n=10$ nodes the leaves are $A[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.

$$
% caption: Processing order of $\textsc{Build-Max-Heap}$ on $10$ nodes. Leaves $A[6..10]$
%          are trivial heaps and skipped (grey); the internal nodes $A[5],A[4],\dots,A[1]$
%          are sifted down in decreasing index (red labels), each after its children are
%          already heaps.
\begin{tikzpicture}[
  n/.style={circle, draw, minimum size=7.5mm, font=\small, inner sep=0pt},
  leaf/.style={circle, draw, fill=black!8, minimum size=7.5mm, font=\small, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[n] (a1) at (0,0) {16};
  \node[n] (a2) at (-2.6,-1.4) {14};
  \node[n] (a3) at (2.6,-1.4) {10};
  \node[n] (a4) at (-3.8,-2.8) {8};
  \node[n] (a5) at (-1.4,-2.8) {7};
  \node[leaf] (a6) at (1.4,-2.8) {9};
  \node[leaf] (a7) at (3.8,-2.8) {3};
  \node[leaf] (a8) at (-4.5,-4.2) {2};
  \node[leaf] (a9) at (-3.1,-4.2) {4};
  \node[leaf] (a10) at (-2.0,-4.2) {1};
  \draw (a1)--(a2); \draw (a1)--(a3);
  \draw (a2)--(a4); \draw (a2)--(a5);
  \draw (a3)--(a6); \draw (a3)--(a7);
  \draw (a4)--(a8); \draw (a4)--(a9); \draw (a5)--(a10);
  \node[font=\scriptsize, text=red!75!black, anchor=south] at (0,0.5) {step 5};
  \node[font=\scriptsize, text=red!75!black, anchor=east] at (-3.0,-1.4) {step 4};
  \node[font=\scriptsize, text=red!75!black, anchor=west] at (3.0,-1.4) {step 3};
  \node[font=\scriptsize, text=red!75!black, anchor=east] at (-4.2,-2.8) {step 2};
  \node[font=\scriptsize, text=red!75!black, anchor=west] at (-0.95,-2.8) {step 1};
  \node[font=\scriptsize, text=black, anchor=west] at (4.3,-3.5) {leaves A[6..10]: no work};
\end{tikzpicture}
$$

The loop invariant makes the correctness immediate.

> **Invariant (Build-heap loop).** _At the start of each iteration, every node $i+1, i+2, \dots, n$ is the root
> of a max-heap._

Initialization: nodes $\floor{n/2}+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 $\textsc{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 $\textsc{Build-Max-Heap}$ on the unsorted array
$A = \vector{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}$, with $n = 10$ and first internal
node $\floor{10/2} = 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,
$\vector{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.

$$
% caption: $\textsc{Build-Max-Heap}$ on $\langle 4,1,3,2,16,9,10,14,8,7\rangle$: the array
%          after each iteration $i = 5, 4, \dots, 1$. Shaded cells changed in that step;
%          the loop leaves every suffix a forest of heaps until the whole array is one.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=7mm, font=\small, inner sep=0pt},
  lbl/.style={font=\footnotesize, anchor=east}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i in {1,...,10} \node[font=\scriptsize, text=black] at (\i*0.75,0.62) {\i};
  \node[lbl] at (0.2,0) {start};
  \foreach \v/\i in {4/1,1/2,3/3,2/4,16/5,9/6,10/7,14/8,8/9,7/10} \node[cell] at (\i*0.75,0) {\v};
  \node[lbl] at (0.2,-1.0) {i = 5};
  \foreach \v/\i in {4/1,1/2,3/3,2/4,16/5,9/6,10/7,14/8,8/9,7/10} \node[cell] at (\i*0.75,-1.0) {\v};
  \node[font=\footnotesize, text=black, anchor=west] at (8.15,-1.0) {no swap};
  \node[lbl] at (0.2,-2.0) {i = 4};
  \foreach \v/\i in {4/1,1/2,3/3,16/5,9/6,10/7,8/9,7/10} \node[cell] at (\i*0.75,-2.0) {\v};
  \node[cell, fill=acc!14] at (4*0.75,-2.0) {14};
  \node[cell, fill=acc!14] at (8*0.75,-2.0) {2};
  \node[lbl] at (0.2,-3.0) {i = 3};
  \foreach \v/\i in {4/1,1/2,14/4,16/5,9/6,2/8,8/9,7/10} \node[cell] at (\i*0.75,-3.0) {\v};
  \node[cell, fill=acc!14] at (3*0.75,-3.0) {10};
  \node[cell, fill=acc!14] at (7*0.75,-3.0) {3};
  \node[lbl] at (0.2,-4.0) {i = 2};
  \foreach \v/\i in {4/1,14/4,9/6,3/7,2/8,8/9} \node[cell] at (\i*0.75,-4.0) {\v};
  \node[cell, fill=acc!14] at (2*0.75,-4.0) {16};
  \node[cell, fill=acc!14] at (5*0.75,-4.0) {7};
  \node[cell, fill=acc!14] at (10*0.75,-4.0) {1};
  \node[cell] at (3*0.75,-4.0) {10};
  \node[lbl] at (0.2,-5.0) {i = 1};
  \foreach \v/\i in {10/3,7/5,9/6,3/7,2/8,1/10} \node[cell] at (\i*0.75,-5.0) {\v};
  \node[cell, fill=acc!14] at (1*0.75,-5.0) {16};
  \node[cell, fill=acc!14] at (2*0.75,-5.0) {14};
  \node[cell, fill=acc!14] at (4*0.75,-5.0) {8};
  \node[cell, fill=acc!14] at (9*0.75,-5.0) {4};
  \node[font=\footnotesize, text=acc, anchor=west] at (8.15,-5.0) {max-heap};
\end{tikzpicture}
$$

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

The easy [bound](/algorithms/foundations/asymptotic-analysis) is immediate: there are $O(n)$ calls to $\textsc{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 $\textsc{Max-Heapify}$ has
almost nothing to do.

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

$$
\sum_{h=0}^{\floor{\log_2 n}} \ceil{\frac{n}{2^{h+1}}}\, O(h)
\;=\; O\!\parens{ n \sum_{h=0}^{\infty} \frac{h}{2^{h}} }.
$$

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 = \tfrac12$. 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.[^clrs-build]
Building a heap is asymptotically negligible compared to the sort that follows.

$$
% caption: The geometric cancellation in $\textsc{Build-Max-Heap}$. By height $h$ the node
%          count halves going up ($\le \lceil n/2^{h+1}\rceil$) while per-node work grows
%          only as $O(h)$, so the level totals (right) decay geometrically and sum to
%          $O(n)$.
\begin{tikzpicture}[
  bar/.style={draw, fill=acc!18},
  cnt/.style={draw, fill=black!10}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \h/\nodes/\y in {0/8/0, 1/4/1, 2/2/2, 3/1/3} {
    \node[font=\scriptsize, anchor=east] at (-0.2,\y*0.95) {$h{=}\h$};
    \draw[cnt] (0,\y*0.95-0.28) rectangle ({\nodes*0.28},\y*0.95+0.28);
    \node[font=\scriptsize] at ({\nodes*0.28+0.4},\y*0.95) {$\nodes$};
  }
  \node[font=\footnotesize, anchor=south] at (1.0,3*0.95+0.45) {nodes at height $h$};
  \foreach \tot/\y in {0/0, 4/1, 4/2, 3/3} {
    \draw[bar] (4.2,\y*0.95-0.28) rectangle ({4.2+\tot*0.28},\y*0.95+0.28);
    \node[font=\scriptsize] at ({4.2+\tot*0.28+0.3},\y*0.95) {$\tot$};
  }
  \node[font=\footnotesize, anchor=south] at (5.0,3*0.95+0.45) {work per level};
\end{tikzpicture}
$$

## 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.

```algorithm
caption: $\textsc{Heapsort}(A)$ — sort $A[1..n]$ in place, increasing
number: 3
call $\textsc{Build-Max-Heap}(A)$
for $i \gets A.length$ downto $2$ do
  exchange $A[1]$ with $A[i]$ // max to its final slot
  $A.heapsize \gets A.heapsize - 1$ // evict from the heap
  call $\textsc{Max-Heapify}(A, 1)$ // restore the shrunken heap
```

The array splits into two regions: a heap at the front, $A[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.

$$
% caption: A heapsort snapshot. The array splits into a max-heap prefix
%          $A[1..\text{heapsize}]$ and a sorted suffix; each step swaps the root $A[1]$
%          into the slot just before the suffix, drops the heap size by one, and sifts
%          down.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=7.5mm, font=\small, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \v/\i in {9/1,7/2,3/3,2/4,4/5} \node[cell, fill=acc!15] (h\i) at (\i*0.82,0) {\v};
  \foreach \v/\i in {14/6,16/7} \node[cell, fill=black!10] (s\i) at (\i*0.82,0) {\v};
  \foreach \i in {1,...,7} \node[font=\scriptsize, text=black] at (\i*0.82,-0.62) {\i};
  \node[font=\footnotesize, text=acc] at (2.46,0.9) {max-heap (heapsize $=5$)};
  \node[font=\footnotesize, text=black] at (5.74,0.9) {sorted};
  \draw[acc, thick] (0.6,0.52)--(4.92,0.52);
  \draw[thick, black] (5.0,0.52)--(6.16,0.52);
  \draw[<->, >=Stealth, thick, red!75!black] (h1.250) to[out=-90, in=-90, looseness=0.55] (h5.290);
  \node[font=\scriptsize, text=red!75!black] at (2.46,-1.55) {swap A[1] to slot 5, then evict};
\end{tikzpicture}
$$

> **Invariant (Loop).** At the start of each iteration, $A[1..A.heapsize]$ is a
> max-heap containing the $A.heapsize$ smallest elements, and
> $A[A.heapsize+1 .. n]$ holds the remaining elements in sorted order, each no
> smaller than anything in the heap.

The invariant holds initially because $\textsc{Build-Max-Heap}$ makes all of
$A[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
$\vector{16, 14, 10, 8, 7, 9, 3, 2, 4, 1}$ makes the two-region structure
visible:

$$
% caption: The first three extractions of heapsort. Each row swaps the root into the slot
%          before the sorted suffix (grey), shrinks the heap, and sifts the swapped key
%          down; the suffix accumulates the maxima in increasing order from the right.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=7mm, font=\small, inner sep=0pt},
  done/.style={draw, fill=black!10, minimum size=7mm, font=\small, inner sep=0pt},
  lbl/.style={font=\footnotesize, anchor=east}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i in {1,...,10} \node[font=\scriptsize, text=black] at (\i*0.75,0.62) {\i};
  \node[lbl] at (0.2,0) {built heap};
  \foreach \v/\i in {16/1,14/2,10/3,8/4,7/5,9/6,3/7,2/8,4/9,1/10} \node[cell, fill=acc!8] at (\i*0.75,0) {\v};
  \node[lbl] at (0.2,-1.0) {extract 16};
  \foreach \v/\i in {14/1,8/2,10/3,4/4,7/5,9/6,3/7,2/8,1/9} \node[cell, fill=acc!8] at (\i*0.75,-1.0) {\v};
  \node[done] at (10*0.75,-1.0) {16};
  \node[lbl] at (0.2,-2.0) {extract 14};
  \foreach \v/\i in {10/1,8/2,9/3,4/4,7/5,1/6,3/7,2/8} \node[cell, fill=acc!8] at (\i*0.75,-2.0) {\v};
  \node[done] at (9*0.75,-2.0) {14};
  \node[done] at (10*0.75,-2.0) {16};
  \node[lbl] at (0.2,-3.0) {extract 10};
  \foreach \v/\i in {9/1,8/2,3/3,4/4,7/5,1/6,2/7} \node[cell, fill=acc!8] at (\i*0.75,-3.0) {\v};
  \node[done] at (8*0.75,-3.0) {10};
  \node[done] at (9*0.75,-3.0) {14};
  \node[done] at (10*0.75,-3.0) {16};
  \node[font=\footnotesize, text=black, anchor=west] at (8.15,0) {heap only};
  \node[font=\footnotesize, text=black, anchor=west] at (8.15,-3.35) {sorted tail grows};
\end{tikzpicture}
$$

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 $\vector{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.

> **Claim (Heapsort cost).** $\textsc{Heapsort}$ runs in $\Theta(n\log n)$ time in
> _every_ case — best, average, and worst. $\textsc{Build-Max-Heap}$ is $O(n)$; the
> loop runs $n - 1$ times, each iteration doing $O(1)$ work plus one
> $\textsc{Max-Heapify}$ at $O(\log n)$, so the total is
>
> $$
> O(n) + (n-1)\cdot O(\log n) = \Theta(n\log n).
> $$
>
> There is no easier case, because the heap is always full height during the
> extractions. Heapsort is in place ($O(1)$
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.[^clrs-sort]

::impl{algo="heapsort"}

### Heapsort in practice

Asymptotically, heapsort ties mergesort and beats quicksort's worst
case. Measured on real machines it is slower, for several reasons.[^skiena-pq]

- **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.39\,n\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

- $\textsc{Insert}(S, x)$: add $x$ to $S$;
- $\textsc{Maximum}(S)$: return the element with the largest key;
- $\textsc{Extract-Max}(S)$: remove and return that element;
- $\textsc{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.[^skiena-pq]

```algorithm
caption: $\textsc{Heap-Extract-Max}(A)$ — remove and return the largest key
number: 4
$max \gets A[1]$
$A[1] \gets A[A.heapsize]$ // last leaf to the root
$A.heapsize \gets A.heapsize - 1$
call $\textsc{Max-Heapify}(A, 1)$ // sift the new root down
return $max$
```

$\textsc{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 $\textsc{Increase-Key}$ from $-\infty$: append the new
element as the last leaf, then sift it up.

```algorithm
caption: $\textsc{Heap-Increase-Key}(A, i, k)$ — raise $A[i]$ to $k$ and sift up
number: 5
if $k < A[i]$ then
  error "new key smaller than current key"
$A[i] \gets k$
while $i > 1$ and $A[\parent(i)] < A[i]$ do
  exchange $A[i]$ with $A[\parent(i)]$ // float up one level
  $i \gets \parent(i)$
```

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 $\floor{\log_2 n}$. 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.

$$
% caption: Increase-Key as sift-up, the mirror of Max-Heapify. Raising a leaf's key to
%          $15$ violates the heap above it, so it swaps with its parent repeatedly
%          ($15>8$, then $15>14$) until $15<16$ at the root.
\begin{tikzpicture}[
  n/.style={circle, draw, minimum size=7.5mm, font=\small, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[n] (r) at (0,0) {16};
  \node[n, fill=acc!12] (l) at (-1.9,-1.3) {14};
  \node[n] (rt) at (1.9,-1.3) {10};
  \node[n, fill=acc!12] (ll) at (-2.9,-2.7) {8};
  \node[n] (lr) at (-0.9,-2.7) {7};
  \node[n] (rl) at (0.9,-2.7) {9};
  \node[n] (rr) at (2.9,-2.7) {3};
  \node[n, fill=red!16] (lll) at (-3.5,-4.1) {15};
  \node[n] (llr) at (-2.3,-4.1) {4};
  \draw (r)--(l); \draw (r)--(rt); \draw (l)--(ll); \draw (l)--(lr);
  \draw (rt)--(rl); \draw (rt)--(rr); \draw (ll)--(lll); \draw (ll)--(llr);
  \draw[<->, red, thick] (lll) to[bend left=12] node[left, font=\scriptsize] {1} (ll);
  \draw[<->, red, thick] (ll) to[bend left=12] node[left, font=\scriptsize] {2} (l);
  \node[font=\scriptsize, text=acc, anchor=west] at (0.7,0.3) {stop: $15<16$};
\end{tikzpicture}
$$

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

::impl{algo="max_heap"}

## 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
$\textsc{Decrease-Key}$, called once per edge, and the **Fibonacci heap** (Fredman
and Tarjan, 1984) drives its _amortized_ cost to $O(1)$, with $\textsc{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](/algorithms/sorting/external-sorting)
and [B-trees](/algorithms/data-structures/b-trees): on real memory
hierarchies the branching factor is tuned to the block, not left at $2$.[^skiena-pq]

## Takeaways

- A **binary heap** is a complete binary tree stored as an array; index
  arithmetic ($\parent(i)=\floor{i/2}$, 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.
- $\textsc{Max-Heapify}$ (sift-down) repairs one violation in $O(\log n)$;
  $\textsc{Build-Max-Heap}$ applies it bottom-up in $O(n)$, since work falls
  geometrically while node counts rise geometrically.
- $\textsc{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.

[^clrs-heap]: **CLRS**, Ch. 6 — Heapsort (§6.1). The binary max-heap as a complete tree stored in an array, with the max-heap property and index arithmetic for parent/children.
[^erickson-ds]: **Erickson**, _Algorithms_, Ch. — Data Structures. The sift-down primitive that restores the heap property at one node in $O(\log n)$.
[^clrs-build]: **CLRS**, Ch. 6 — Heapsort (§6.3). $\textsc{Build-Max-Heap}$ runs in $O(n)$, summing geometrically decaying per-level work.
[^clrs-sort]: **CLRS**, Ch. 6 — Heapsort (§6.4). $\textsc{Heapsort}$ sorts in place in $\Theta(n\log n)$ in all cases by repeatedly extracting the maximum.
[^skiena-pq]: **Skiena**, _The Algorithm Design Manual_, §4.3, §12.2 — Heaps and Priority Queues. The heap implements a priority queue with $O(1)$ maximum and $O(\log n)$ updates.