GATE CS 2015 Set 2 Q17 — Binary Heaps

Since the left and right subtrees of the root are already max-heaps, only the root element itself can violate the max-heap property. To convert the entire complete binary tree into a max-heap, we only need to perform a single Max-Heapify operation starting at the root.

The Max-Heapify procedure compares the root with its children, swaps it with the larger child if necessary, and recursively heapifies the affected subtree. In the worst case, the root element must travel down to a leaf node.

For a complete binary tree of $n$ nodes, the height is $h = heta(\log n)$. The number of comparisons and swaps in the worst case is proportional to this height. Thus, the worst-case complexity is $\Theta(\log n)$, which gives a tight lower bound of $\Omega(\log n)$ operations.