= Solution
Store a <complete binary tree> in a one-indexed <array> $A[1..n]$, level by level. Index $i$ has <parent in a rooted tree> $\lfloor i/2\rfloor$ for $i>1$ and possible <children in a rooted tree> $2i$ and $2i+1$, present only when their indices are at most $n$. The <max-heap> condition is $A[\lfloor i/2\rfloor]\ge A[i]$ for every $i>1$.
Following these inequalities from the <root of a tree> to any entry proves that \b[$A[1]$ is a <maximum>]. The <heap order> does not sort siblings or unrelated branches. The <complete binary tree> has height $\lfloor\log_2 n\rfloor$, which bounds how far any single repair can travel. Store the current heap size separately from the <array>'s capacity.
Back to article page
