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

Assume the subtrees rooted at the children in a rooted tree of $i$ already obey the max-heap condition. Compare $A[i]$ with each present child and choose an index of the largest of these at most three keys. If that index is $i$, stop. Otherwise exchange the two keys, continue at the chosen child, and repeat. This is sift down, with the inequality reversed from a minimum-oriented binary heap.

The exchange repairs the old root position because its new key dominates both child roots; only the subtree receiving the displaced key can still be defective. This recursion invariant proves correctness. Each exchange descends one level and costs constant work, so the worst-case running time is $O(h)$ for subtree height $h$, hence $O(\log n)$. A small key at the root of a suitably ordered heap must descend to a leaf, so the logarithmic worst-case bound is attained.