Consider a binary max-heap implemented using an array. Which one of the…

2006

Consider a binary max-heap implemented using an array. Which one of the following arrays represents a binary max-heap?

  1. A.

    23, 17, 14, 6, 13, 10, 1, 12, 7, 5

  2. B.

    23, 17, 14, 6, 13, 10, 1, 5, 7, 12

  3. C.

    23, 17, 14, 7, 13, 10, 1, 5, 6, 12

  4. D.

    23, 17, 14, 7, 13, 10, 1, 12, 5, 7

Attempted by 159 students.

Show answer & explanation

Correct answer: C

Explanation:

A binary max-heap stored in an array requires each parent node to be greater than or equal to its children. Using 1-based indexing, for every parent at index i (1 ≤ i ≤ floor(n/2)), the following must hold: A[i] >= A[2i] and A[i] >= A[2i + 1] (if that child exists).

Check the candidate array 23, 17, 14, 7, 13, 10, 1, 5, 6, 12 by verifying each parent:

  1. Index 1: 23 >= 17 and 14 — OK.

  2. Index 2: 17 >= 7 and 13 — OK.

  3. Index 3: 14 >= 10 and 1 — OK.

  4. Index 4: 7 >= 5 and 6 — OK.

  5. Index 5: 13 >= 12 (only left child exists) — OK.

Conclusion: The array 23, 17, 14, 7, 13, 10, 1, 5, 6, 12 satisfies the max-heap property and therefore represents a binary max-heap.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir