Show that the worst-case running time of MAX-HEAPIFY on a heap of size \(n\) is \(\Omega(\lg n)\). (Hint: For a heap with \(n\) nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a simple path from the root down to a leaf.)

Suppose \(i = 1\) and \(A[i]\) is the smallest value in the entire heap. Calling MAX-HEAPIFY(\(A, 1\)) will result in the node at the head being swapped repeatdely until it reaches a leaf (and because we’re discussing a worst-case scenario, this leaf will be at the bottom-most level). This means we will perform \(h\) swaps and since \(h = \lfloor \lg n \rfloor\), MAX-HEAPIFY has worst-case run time of \(\Omega(\lg n)\).