= Solution
Count pairwise exchanges in the implementation from part (b), including the initial root/final-leaf exchange. For $n\ge4$, the final leaf has a nonroot parent whose key is strictly larger than the leaf's key. That parent remains after deletion. If the moved leaf could stay at the root without a downward exchange, it would dominate both root children and hence every remaining descendant, contradicting that larger remaining parent. Thus at least one <heapify down> exchange is necessary.
One downward exchange suffices. The following level-order <array> is a <max-heap> on keys one through fifteen:
$$
H=[15,14,13,9,8,12,11,1,2,3,4,5,6,7,10].
$$
Every parent is larger than both children. Exchange the root key fifteen with the final key ten, remove fifteen, then exchange ten with the larger root child fourteen. Ten now has children nine and eight, so repair stops. The final <array> is
$$
[14,10,13,9,8,12,11,1,2,3,4,5,6,7].
$$
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/functional-programming-2014-heap.png]
{title=A fifteen-key max-heap achieving the minimum two pairwise exchanges during maximum deletion}
Hence the <best-case maximum deletion in a binary heap> is
$$
\boxed{\text{two pairwise exchanges for }n\ge4:\ \text{one root/last exchange and one downward exchange}.}
$$
This best case can be arranged at any such size: make the root child on the opposite side from the old final leaf the largest remaining key, the old leaf smaller than its own ancestors but larger than all descendants of that opposite child, and fill the remaining positions in decreasing order along each branch. The promoted child then allows the leaf to stop at depth one.
For sizes two and three, one initial exchange can suffice; for size one no exchange between distinct positions is needed. If only exchanges during <heapify down> are counted, the answer for $n\ge4$ is one. In the fifteen-key example the two exchanges involve three distinct keys, namely fifteen, ten and fourteen. An implementation that moves a hole by assignments need not perform literal swaps, so the count is explicitly tied to the exchange implementation. The worst-case <time complexity> remains logarithmic even though this best-case repair is constant.
Back to article page
