CLRS Solutions | Exercise 6.5-6

Each exchange operation on line 5 of $\textsc{Heap-Increase-Key}$ typically requires three assignments. Show how to use the idea of the inner loop of $\textsc{Insertion-Sort}$ to reduce the three assignments down to just one assignment.

The standard $\textsc{Heap-Increase-Key}$ procedure swaps elements at each step, which requires three assignments (using a temporary variable). We can optimize this using the same technique as insertion sort: instead of swapping at each step, we save the key being moved and shift parent values down, making only one assignment per iteration.

Here’s the original version with swaps:

$$\textsc{Heap-Increase-Key}(A, i, key)$$$$\begin{aligned} 1& \quad \textbf{if }\,key\,<\,A[i] \\ 2& \quad \qquad \textbf{error }\text{\textquotedblleft new key is smaller than current key\textquotedblright} \\ 3& \quad A[i]\,=\,key \\ 4& \quad \textbf{while }\,i\,>\,1\textbf{ and }\,A[\textsc{Parent}(i)]\,<\,A[i] \\ 5& \quad \qquad \text{exchange}\,A[i]\,\text{with}\,A[\textsc{Parent}(i)]\quad \textbf{/\!/} 3\text{ assignments}\, \\ 6& \quad \qquad i\,=\,\textsc{Parent}(i) \\ \end{aligned}$$

The exchange operation on line 5 requires three assignments: temp = A[i], A[i] = A[Parent(i)], and A[Parent(i)] = temp.

Here’s the optimized version using insertion sort’s technique:

$$\textsc{Heap-Increase-Key}'(A, i, key)$$$$\begin{aligned} 1& \quad \textbf{if }\,key\,<\,A[i] \\ 2& \quad \qquad \textbf{error }\text{\textquotedblleft new key is smaller than current key\textquotedblright} \\ 3& \quad \textbf{while }\,i\,>\,1\textbf{ and }\,A[\textsc{Parent}(i)]\,<\,key \\ 4& \quad \qquad A[i]\,=\,A[\textsc{Parent}(i)]\quad \textbf{/\!/} 1\text{ assignment}\, \\ 5& \quad \qquad i\,=\,\textsc{Parent}(i) \\ 6& \quad A[i]\,=\,key \\ \end{aligned}$$

In this optimized version, we:

Compare the new key directly with parent values (not with $A[i]$, which changes during the loop).
Shift parent values down into the child position (only one assignment per iteration).
After the loop terminates, place the key in its final position.

This reduces the number of assignments from $3h$ to $h + 1$ in the worst case, where $h$ is the number of levels the element bubbles up. For a heap with $n$ elements, where $h = O(\lg n)$, this represents a meaningful constant-factor improvement.