- The smallest element in a max-heap is always at a leaf node – TRUE because by definition of a max-heap every parent node must be larger than its child node.
- The second largest element in a max-heap is always a child of a root node – TRUE. The $k^{\text{th}}$ largest element cannot have more than $k-1$ parents (larger value nodes) and so cannot be lower than level $k.$
- A max-heap can be constructed from a binary search tree in $\Theta(n)$ time. Build heap for any array of size $n$ (even unsorted) can be done in $O(n)$ time.
Now lets see the $4^{\text{th}}$ statement.
- A binary search tree can be constructed from a max-heap in $\Theta(n)$ time. This can be proved $\textsf{FALSE}$ using the simple argument that we can do max-heap construction in $O(n)$ and if we can convert this to $\textsf{BST}$ in $O(n)$ time we can do an inorder traversal of $\textsf{BST}$ in $O(n)$ time and thus we manage to sort $n$ elements in $O(n)$ time using just comparisons which is known to take at least $\Omega(n \log n)$ time.
An example construction of $\textsf{BST}$ from a max-heap.
Max – Heap
Max Heap Array Representation: $$\begin{array}{|l|l|}\hline \text{Value} &7&4&6&1&3&2&5 \\\hline \text{Array Index} & 1&2&3&4&5&6&7 \\\hline \end{array}$$
Make binary search tree using Array Representation:
- Pick elements from $A[1]$ to $A[7]$ one by one.
- Compare with all previous elements and find its respective place.
We’ll get Binary Search Tree as follows:
Number of comparisons in the worst case for each element $=\underbrace{ \underset{\text{0}}{1} \quad \underset{\text{1}}{2} \quad \underset{\text{2}}{3} \quad \underset{\text{3}}{4} \quad \underset{\text{4}}{5} \quad \underset{\text{5}}{6} \quad \underset{\text{6}}{7}}^{\text{Elements}}_{\textbf{Comparisons}}$
So for $n$ element heap the total no of comparisons could be
$=0+1+2+\dots (n-2)+(n-1)$
$=\Theta \frac{(n-1)n}{2}$
$=\Theta (n^2)$
Note: Option IV: Proof by contradiction: Say you can somehow convert any arbitrary heap into a BST in $O(n)$ time.
It is already known that any arbitrary list can be converted into a heap in $O(n)$ time, and that the in-order traversal of BST is always sorted. So effectively we have sorted the array in linear time using comparison based sorting technique, but that is not possible as any comparison based sorting requires $\Omega(n \log n)$ time. That is a contradiction.
By using more efficient method this time complexity could be reduced to $O( n.\log n)$ but it can never be $ O(n)$.
OPTION A is the correct answer.
