Which of the following sequences of array elements forms a heap?

2006

Which of the following sequences of array elements forms a 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 216 students.

Show answer & explanation

Correct answer: C

Key idea: For a max-heap stored in an array (0-based), each parent at index i must be greater than or equal to its children at indices 2i+1 and 2i+2.

Check the candidate array {23, 17, 14, 7, 13, 10, 1, 5, 6, 12}:

  1. Index 0: parent = 23, children = 17 and 14 → 23 >= 17 and 23 >= 14 (OK).

  2. Index 1: parent = 17, children = 7 and 13 → 17 >= 7 and 17 >= 13 (OK).

  3. Index 2: parent = 14, children = 10 and 1 → 14 >= 10 and 14 >= 1 (OK).

  4. Index 3: parent = 7, children = 5 and 6 → 7 >= 5 and 7 >= 6 (OK).

  5. Index 4: parent = 13, child = 12 (only left child for this index) → 13 >= 12 (OK).

Because every parent is greater than or equal to its children, the array satisfies the max-heap property and is therefore a valid heap.

Conclusion: The sequence {23, 17, 14, 7, 13, 10, 1, 5, 6, 12} is a valid max-heap.

Explore the full course: Gate Guidance By Sanchit Sir