Consider the array representation of a binary min-heap containing 1023…
2020
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 _________ .
Attempted by 153 students.
Show answer & explanation
Correct answer: 511
Key idea: In a min-heap every parent is less than or equal to its children, so the maximum element must be one of the leaves.
Count the leaves: For a heap of n elements, internal nodes are at indices 1..floor(n/2), so the leaves are the remaining nodes. With n = 1023, floor(1023/2) = 511, so leaves = 1023 − 511 = 512.
Find the maximum among the 512 leaves: any algorithm must perform at least 511 comparisons (e.g., compare sequentially or via a tournament), since finding the maximum among m items requires at least m − 1 comparisons.
Answer: 511 comparisons.