Project ForgeSign up free
Data Structures
Trees
GATE 2009
Medium

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

  • A{25, 12, 16, 13, 10, 8, 14}
  • B{25, 14, 13, 16, 10, 8, 12}
  • {25, 14, 16, 13, 10, 8, 12}
  • D{25, 14, 12, 13, 10, 8, 16}

Explanation

Checking the max-heap property (parent ≥ both children) at every internal node for {25,14,16,13,10,8,12} (0-indexed, children of i at 2i+1,2i+2): root25≥14,16 ✓; index1(14)≥13,10 ✓; index2(16)≥8,12 ✓. All satisfied. The other three options each fail at least one parent-child check.

Source: GATE CS 2009 (2009)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free