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 / iii / Solution

Leaves already obey the heap order. Process indices $\lfloor n/2\rfloor ,\lfloor n/2\rfloor -1,\dots ,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$. ThereforeThe total repair work is thus $O(n)$, and the loop itself has a linear number of iterations, giving $\Theta (n)$ for this bottom-up heap construction. Most nodes are near the leaves and require little repair.