Question

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

• A. \( 20, 18, 15, 12, 10, 9, 16 \)
• B. \( 20, 18, 12, 10, 9, 15, 16 \)
• C. \( 20, 12, 18, 10, 9, 15, 16 \)
• D. \( 20, 12, 15, 10, 9, 16, 18 \)

Hint:

A Binary Max-Heap must maintain: 1. Complete Binary Tree Structure 2. Heap Property: Parent node must be greater than or equal to its children.

Answer 1

The Correct Option is A

Step 1: Understanding Max-Heap Property - A binary max-heap is a complete binary tree where the value of each parent node is greater than or equal to its children. - The heap is stored in an array such that: - Parent at index \( i \) has children at indices: \[ \text{Left Child} = 2i + 1, \quad \text{Right Child} = 2i + 2 \]
Step 2: Checking Each Option for Max-Heap Property Option (A): \( 20, 18, 15, 12, 10, 9, 16 \) \begin{itemize} \item Parent-child relationships: \begin{itemize} \item 20 (root) \( \geq \) 18, 15 \item 18 \( \geq \) 12, 10 \item 15 \( \geq \) 9, 16 \end{itemize} \item Valid Max-Heap \end{itemize} 2. Option (B): \( 20, 18, 12, 10, 9, 15, 16 \) \begin{itemize} \item 12 is a parent of 15, but 12 \(<\) 15 \item Not a Max-Heap \end{itemize} 3. Option (C): \( 20, 12, 18, 10, 9, 15, 16 \) \begin{itemize} \item 12 is a parent of 18, but 12 \(<\) 18 \item Not a Max-Heap \end{itemize} 4. Option (D): \( 20, 12, 15, 10, 9, 16, 18 \) \begin{itemize} \item 15 is a parent of 16, but 15 \(<\) 16 \item Not a Max-Heap \end{itemize}