CLRS Solutions | Exercise 6.2-2

Starting with the procedure $\textsc{Max-Heapify}$, write pseudocode for the procedure $\textsc{Min-Heapify}(A, i)$, which performs the corresponding manipulation on a min-heap. How does the running time of $\textsc{Min-Heapify}$ compare to that of $\textsc{Max-Heapify}$?

The key difference between a min-heap and a max-heap is the heap property: in a min-heap, each parent must be smaller than (or equal to) its children, whereas in a max-heap each parent must be larger. So $\textsc{Min-Heapify}$ needs to ensure that the smallest value bubbles up to the parent position, rather than the largest.

The logic is symmetric to $\textsc{Max-Heapify}$. Instead of finding the largest among the node and its children, we find the smallest. If the current node is not the smallest, we exchange it with the smallest child and recursively fix the violated subtree.

$$\textsc{Min-Heapify}(A, i)$$$$\begin{aligned} 1& \quad l\,=\,\textsc{LEFT}(i) \\ 2& \quad r\,=\,\textsc{RIGHT}(i) \\ 3& \quad \textbf{if }\,l\,\leq\,A.heap\text{-}size\textbf{ and }\,A[l]\,<\,A[i] \\ 4& \quad \qquad smallest\,=\,l \\ 5& \quad \textbf{else }\,smallest\,=\,i \\ 6& \quad \textbf{if }\,r\,\leq\,A.heap\text{-}size\textbf{ and }\,A[r]\,<\,A[smallest] \\ 7& \quad \qquad smallest\,=\,r \\ 8& \quad \textbf{if }\,smallest\,\ne\,i \\ 9& \quad \qquad \text{exchange}\,A[i]\,\text{with}\,A[smallest] \\ 10& \quad \qquad \textsc{Min-Heapify}(A, \, smallest) \\ \end{aligned}$$

The changes from $\textsc{Max-Heapify}$ are minimal:

We renamed largest to smallest
We changed the comparison operators from > to <
Everything else remains the same

The running time of $\textsc{Min-Heapify}$ is identical to that of $\textsc{Max-Heapify}$. Both procedures perform the same number of operations: constant-time comparisons and exchanges at each level, plus a recursive call that moves down the tree. Since the structure and depth of a min-heap is the same as a max-heap with the same number of elements, the running time is $O(h)$ where $h$ is the height of the node, or $O(\lg n)$ for a heap with $n$ elements.