The GATE Grind

GATE 2020 CS – Question 57

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 ______.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 511 to 511

Explanation

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

All Binary Heaps questions →