Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is …
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2020 · Q47
Time
Your answerNumerical answer
Solution
Official answer: 511
Binary HeapsIn a binary min-heap, the minimum element is stored at the root, and for any node, its value is less than or equal to the values of its children.
Consequently, the maximum element must be located at one of the leaf nodes.
### 1. Count the number of leaf nodes: For a complete binary tree with elements:
(The leaves occupy indices to ).
### 2. Finding the maximum among the leaves: To find the maximum element among candidates, we need to perform pairwise comparisons:
For leaves:
Thus, the answer is 511.
Try the question first, then check your work.
Examiner trap
In a min-heap, where can the maximum element reside? Find how many such candidate positions exist and how many comparisons are needed to find the maximum among them.
This Binary Heaps previous year question is Q47 of the GATE CSE 2020 paper. Find more GATE CSE PYQs on Binary Heaps in Programming and Data Structures, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Binary Heaps PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Binary Heaps has 15 GATE CSE PYQs across 13 papers from 2011 to 2026. 2 of them are 2-mark NAT questions like this one, and it is the only one in GATE CSE 2020.
How GATE tests Binary HeapsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.