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