GATE CS 2019 Set 1 — Question 50

Statement I is TRUE: In a max-heap, every parent node is greater than or equal to its children. Therefore, the smallest element must be in a node that has no children (a leaf node), otherwise, its children would be smaller than it, violating the max-heap property.Statement II is TRUE: The root contains the largest element. The second largest element must be one of the children of the root because any other node in the heap is a descendant of one of these children and thus smaller than or equal to them.Statement III is TRUE: A Binary Search Tree (BST) can be converted to a sorted array in $\Theta(n)$ time using in-order traversal. A max-heap can be built from an array in $\Theta(n)$ time. Thus, the total time is $\Theta(n)$.Statement IV is FALSE: Constructing a BST from a max-heap is equivalent to sorting. We can extract the maximum element $n$ times from the heap, which takes $\Theta(n \log n)$, to get a sorted sequence, and then build a BST. The lower bound for comparison-based sorting is $\Omega(n \log n)$, so we cannot do this in $\Theta(n)$ generally.Therefore, statements I, II, and III are true.