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

Given the target's current heap index $i$, remove it as follows. If $i=n$, discard the last entry. Otherwise replace $A[i]$ by $A[n]$ and reduce $n$ by one. If the replacement is larger than its parent in a rooted tree, use sift up; otherwise use the maximum-oriented sift down from $i$.

Only comparisons incident to the replacement can initially violate the heap order. If it exceeds its parent, it also dominates the old children because the old key dominated those children and was no larger than the parent; an upward repair suffices. Otherwise the upward comparison is valid and only a downward repair can be needed. Thus removal takes $O(\log n)$ worst-case time after the location is known. Searching an unindexed heap for an arbitrary specified key can instead require $\Theta (n)$ time; the logarithmic bound does not include such a search.