Programming and Data Structures · Binary Heaps · 2 marks · Numerical answer
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 ______.
In a binary min-heap the smallest element is at the root, and the **maximum must be at a leaf** (an internal node is smaller than its children).
With $1023=2^{10}-1$ elements the heap is a complete binary tree with 10 levels. The leaves occupy indices $\lfloor1023/2\rfloor+1=512$ to $1023$: that is $512$ leaves.
Finding the maximum of 512 items needs $512-1=\mathbf{511}$ comparisons.
More Binary Heaps questions
GATE 2018 CS Q56– The number of possible min-heaps containing each value from \1,2,3,4,5,6,7\ exactly once…
GATE 2015 CS (CS1) Q37– Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Array…
GATE 2016 CS (CS1) Q47– An operator `delete(i)` for a binary heap data structure is to be designed to delete the…
GATE 2014 CS (CS2) Q22– A max-heap priority queue initially has level order 10,8,5,3,2. Insert 1 then 7. Find the…
GATE 2016 CS (CS2) Q44– A complete binary min-heap contains each integer 1 through 1023 once. Root depth is zero.…
GATE 2011 CS Q33– A max-heap has parent values at least their children’s values. Which displayed tree is a…