Question 50

Statement I: In a max-heap, every node is greater than or equal to its children ($A[\text{parent}] \ge A[\text{child}]$). If the smallest element were at an internal node, its children would have to be smaller than it, contradicting that it is the smallest element. Thus, the smallest element must be at a leaf node. (TRUE)

Statement II: The root holds the maximum element. The second largest element cannot be dominated by any element other than the root. Therefore, it must be located directly at one of the children of the root (index 1 or 2). (TRUE)

Statement III: To construct a max-heap from a BST of $n$ elements, we can extract the $n$ elements via inorder traversal in $\Theta(n)$ time and place them into an array. Then, running Floyd's build_max_heap on the array takes $\Theta(n)$ time. The total time is $\Theta(n)$. (TRUE)

Statement IV: If a BST could be constructed from a max-heap in $\Theta(n)$ time, then since an inorder traversal of a BST outputs elements in sorted order in $\Theta(n)$ time, we would be able to sort an arbitrary array in $\Theta(n)$ comparison time (build max-heap in $\Theta(n)$, construct BST in $\Theta(n)$, traverse BST in $\Theta(n)$). This contradicts the well-established $\Omega(n \log n)$ lower bound for comparison-based sorting. Hence, a BST cannot be constructed from a max-heap in $\Theta(n)$ time in general. (FALSE)

Thus, statements I, II, and III are TRUE.