= Solution
Leaves already obey the <heap order>. Process indices $\lfloor n/2\rfloor,\lfloor n/2\rfloor-1,\ldots,1$, calling the preceding repair at each. When an index is processed, its descendants have already been processed, so the repair's precondition holds. The resulting <array> is a <max-heap>.
The bound obtained by charging $O(\log n)$ to every call is unnecessarily large. The number of nodes with height at least $h$ is at most $\lfloor n/2^h\rfloor$. Therefore
$$
\sum_v(1+\operatorname{height}(v))
\le n+\sum_{h\ge1}\lfloor n/2^h\rfloor<2n.
$$
The total repair work is thus \b[$O(n)$], and the loop itself has a linear number of iterations, giving \b[$\Theta(n)$] for this <bottom-up heap construction>. Most nodes are near the leaves and require little repair.
Back to article page
