The GATE Grind

GATE 2019 CS – Question 50

Algorithms · Searching, Sorting and Hashing · 2 marks · Multiple choice

Consider the following statements:

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 $\Theta(n)$ time

IV. A binary search tree can be constructed from a max-heap in $\Theta(n)$ time

Which of the above statements are TRUE?

  1. I, II and III
  2. I, II and IV
  3. I, III and IV
  4. II, III and IV

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) I, II and III

Explanation

In a max-heap every internal node is at least as large as its children, so the minimum is at a leaf (I). The second largest is one of the root's two children (II). Building a heap from any $n$ elements, including those in a BST, takes $\Theta(n)$ (III). A BST cannot be built from a heap in $\Theta(n)$ because that would sort the elements faster than $\Omega(n\log n)$ (IV is false).