The GATE Grind

GATE 2024 CS (CS1) – Question 43

Programming and Data Structures · Binary Heaps · 2 marks · Multiple choice

Consider a binary min-heap containing 105 distinct elements. Let $k$ be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of $k$ is

  1. 53
  2. 52
  3. 27
  4. 1

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) 53

Explanation

In a min-heap the maximum must be at a leaf. With n=105, leaves occupy indices ⌊105/2⌋+1 = 53 through 105, giving 53 possible values.