GATE CSE 2024 | Set 1 | Question: 33

Question

Consider a binary min-heap containing $105$ distinct elements. Let $k$ be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of $k$ is

• A. $53$
• B. $52$
• C. $27$
• D. $1$ 

Comments

$Ans: A) \ 53$

$42$ (2nd last level) + $11$ (last level) = $53$ possible values of $k$.

---

they are asking no of poosible values of k which is 53  so the no. of possible value is 1(only 53)

i marked like this @Sachin Mittal 1

---

During the exam, I didn't know how to solve this so I took a small example by taking 4 distinct elements then 5 then 6, and then 7 after that I generalized the formula and got the answer.

Answer 1

A binary heap is a complete binary tree.

A binary min-heap satisfies min-heap property. This implies that the maximum element can be in the leaves only.

No. of internal nodes in 105 element heap = $floor(\frac{105}{2}) = 52$.

No. of leaves = 105 - 52 = 53.

Answer - A

Answer 2

its Actually pretty easy. 

Just remember that the number of leaf nodes in any Complete Binary Tree is given by the formula

ceil( Total no. of nodes/2) , which is in this case, 53 where each element is a node. 

Maximum element is bound to be among the leaf nodes only. That is a common sense. If it was at 2nd last level, it cannot be Maximum element.