Project ForgeConsider the following statements about a max-heap:
I. The smallest element in a max-heap is always at a leaf node. II. The second largest element in a max-heap is always a child of the root node. III. A max-heap can be constructed from a binary search tree in Θ(n) time. IV. A binary search tree can be constructed from a max-heap in Θ(n) time.
Which of the above statements are TRUE?
- I, II and III
- BI, II and IV
- CI, III and IV
- DII, III and IV
Explanation
I is TRUE: if the minimum element had a child, that child would have to be ≤ it (violating that it's the minimum) — so it must be a leaf. II is TRUE: the second-largest element can only be 'blocked' from being the largest by one ancestor (the root itself); if it were any deeper, its parent would also have to exceed it, but only the root can exceed the second-largest, forcing it to be a direct child of the root. III is TRUE: an in-order traversal of the BST gives all n values in sorted order in Θ(n) time, and building a heap array from n given values via the standard bottom-up heapify procedure also takes Θ(n). IV is FALSE: a max-heap only encodes parent≥child relationships, not a full sorted order — extracting a fully sorted arrangement (needed to build a BST) from a heap requires heap-sort-style extraction, which takes Θ(n log n), not Θ(n).
Source: GATE CS 2019 (Set-2) (2019)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.