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 ____.
GATE 2020 CS Q.47: solution and answer
Answer and solution
ANSWER
The minimum number of comparisons required is 511.
Official answer: 511Source: Official answer key, GATE 2020 CS (IIT Delhi)
Min-heap property: every parent's value is ≤ its children's values. Therefore no internal (non-leaf) node can be the maximum — following any root-to-leaf path, values are non-decreasing, so the maximum overall must occur at some leaf.
For n = 1023 = 2^10 - 1 elements, the array-represented heap is a perfect binary tree with 10 levels (height 9).
In a 1-indexed array representation of a heap of size n, the leaves occupy indices floor(n/2)+1 through n, so the number of leaves is n - floor(n/2) = ceil(n/2). For n = 1023: ceil(1023/2) = 1023 - 511 = 512.
The min-heap property gives no ordering information among values in different leaf positions (only along root-to-leaf paths), so the maximum could be any one of these 512 leaves — all 512 must be compared against one another to determine which is largest.
Finding the maximum of a set of k elements by pairwise comparison requires exactly k-1 comparisons in the minimum case (a tournament/linear-scan elimination: each comparison rules out at most one candidate, and k-1 candidates must be ruled out).
With k = 512 leaves, the minimum number of comparisons required = 512 - 1 = 511.
KEY IDEA
In a min-heap, every parent is ≤ its children, so the maximum element can only be among the leaf nodes (an internal node always has a descendant chain going down to a leaf with values ≥ it, so it can never be the largest). Finding the maximum of any set of unordered elements needs exactly comparisons in the best case (tournament method), and no heap-order information helps distinguish among the leaves since min-heap order says nothing about relative order among sibling subtrees.
WATCH OUT FOR
Assuming the maximum can be found using standard heap operations, or forgetting that in a min-heap the maximum could be any one of the leaf nodes — leading to miscounting the leaves (e.g., using floor(n/2) instead of ceil(n/2)) or forgetting the k−1 lower bound for finding a maximum among unordered elements.
From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes
More Trees & heaps questions
- GATE 2018 CS Q.46 · NAT · 2 marksThe number of possible min-heaps containing each value from 1, 2, 3, 4, 5, 6, 7 exactly once is.
- GATE 2026 CS1 Q.23 · MSQ · 1 markLet n be an odd number greater than 100. Consider a binary minheap with n elements stored in an array P…
- GATE 2026 CS1 Q.33 · NAT · 1 markThe height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree.
- GATE 2026 CS1 Q.40 · MCQ · 2 marksLet P be the set of all integers from 1 to 15. Consider any order of insertion of the elements of P into a…