= 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 \b[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.
Back to article page
