CLRS Solutions | Exercise 6.2-5

The code for $\textsc{Max-Heapify}$ is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient $\textsc{Max-Heapify}$ that uses an iterative control construct (a loop) instead of recursion.

The recursive version of $\textsc{Max-Heapify}$ is an example of tail recursion, where the recursive call is the last operation in the procedure. Tail-recursive procedures can always be converted to iterative ones by using a loop. The key insight is that instead of making a recursive call with a new index, we simply update the index variable and continue looping.

In the recursive version, if we need to recurse on a child, we call $\textsc{Max-Heapify}(A, \textit{largest})$. In the iterative version, we instead set $i = \textit{largest}$ and repeat the process. We continue until the heap property is satisfied (when largest equals $i$), at which point we exit the loop.

$$\textsc{Max-Heapify}(A, i)$$$$\begin{aligned} 1& \quad \textbf{while }\,i\,\leq\,A.heap\text{-}size\,/\,2 \\ 2& \quad \qquad l\,=\,\textsc{Left}(i) \\ 3& \quad \qquad r\,=\,\textsc{Right}(i) \\ 4& \quad \qquad \textbf{if }\,l\,\leq\,A.heap\text{-}size\textbf{ and }\,A[l]\,>\,A[i] \\ 5& \quad \qquad \qquad largest\,=\,l \\ 6& \quad \qquad \textbf{else }\,largest\,=\,i \\ 7& \quad \qquad \textbf{if }\,r\,\leq\,A.heap\text{-}size\textbf{ and }\,A[r]\,>\,A[largest] \\ 8& \quad \qquad \qquad largest\,=\,r \\ 9& \quad \qquad \textbf{if }\,largest\,=\,i \\ 10& \quad \qquad \qquad \textbf{return } \\ 11& \quad \qquad \text{exchange}\,A[i]\,\text{with}\,A[largest] \\ 12& \quad \qquad i\,=\,largest \\ \end{aligned}$$

The loop continues as long as $i$ is not a leaf (i.e., $i \leq A.\textit{heap-size}/2$). This is because once we reach a leaf, there are no children to compare with, and the heap property is automatically satisfied.

Inside the loop, we perform the same comparisons as the recursive version to find the largest among the node and its children. If the largest is the current node itself, we exit immediately via return. Otherwise, we exchange the values and update $i$ to point to the child where we moved the violating element, then continue the loop.

The iterative version has the same asymptotic time complexity $O(\lg n)$ as the recursive version, but it avoids the overhead of recursive function calls. This includes avoiding stack frame allocation, parameter passing, and return address management. For deep heaps, this can provide a noticeable performance improvement, especially on systems where function call overhead is significant.