CLRS Solutions | Exercise 6.5-8

The operation $\textsc{Heap-Delete}(A, i)$ deletes the item in node $i$ from heap $A$. Give an implementation of $\textsc{Heap-Delete}$ that runs in $O(\lg n)$ time for an $n$-element max-heap.

Deleting an arbitrary element from a heap is similar to $\textsc{Heap-Extract-Max}$, except we’re removing from any position rather than just the root. The strategy is to replace the element to be deleted with the last element in the heap, then restore the heap property.

The key insight is that after replacement, the heap property might be violated in two ways:

The new value might be too large (larger than its parent), requiring upward movement
The new value might be too small (smaller than its children), requiring downward movement

We can handle both cases efficiently.

$$\textsc{Heap-Delete}(A, i)$$$$\begin{aligned} 1& \quad \textbf{if }\,i\,>\,A.heap\text{-}size \\ 2& \quad \qquad \textbf{error }\text{\textquotedblleft index out of bounds\textquotedblright} \\ 3& \quad \textbf{if }\,i\,=\,A.heap\text{-}size \\ 4& \quad \qquad A.heap\text{-}size\,=\,A.heap\text{-}size\,-\,1 \\ 5& \quad \qquad \textbf{return } \\ 6& \quad A[i]\,=\,A[A.heap\text{-}size] \\ 7& \quad A.heap\text{-}size\,=\,A.heap\text{-}size\,-\,1 \\ 8& \quad \textbf{if }\,i\,>\,1\textbf{ and }\,A[i]\,>\,A[\textsc{Parent}(i)] \\ 9& \quad \qquad \textsc{Heap-Increase-Key}(A, \, i, \, A[i]) \\ 10& \quad \textbf{else } \\ 11& \quad \qquad \textsc{Max-Heapify}(A, \, i) \\ \end{aligned}$$

Why This Works

After replacing $A[i]$ with the last element, exactly one of three situations occurs:

The heap property is already satisfied at position $i$ (the replacement value happens to fit perfectly)
The new value is too large compared to its parent (violates the max-heap property upward)
The new value is too small compared to its children (violates the max-heap property downward)

The conditional on line 8 distinguishes case 2 from case 3. If neither condition is met, $\textsc{Max-Heapify}$ handles case 3 (and does nothing for case 1).

Time Complexity

The running time is $O(\lg n)$ because:

The replacement and comparison operations take $O(1)$ time
Either $\textsc{Heap-Increase-Key}$ or $\textsc{Max-Heapify}$ is called, each taking $O(\lg n)$ time