Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 6 / a / i / Solution

Store a complete binary tree in a one-indexed array $A[\mathrm{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 $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.