GATE CSE 2023 | Question: 2

Question

Which one of the following sequences when stored in an array at locations $A[1], \ldots, A[10]$ forms a max-heap?

• A. $23,17,10,6,13,14,1,5,7,12$
• B. $23,17,14,7,13,10,1,5,6,12$
• C. $23,17,14,6,13,10,1,5,7,15$
• D. $23,14,17,1,10,13,16,12,7,5$

Comments

B is answer

---

The correct answer is Option B

---

B is the correct Ans

---

https://gateoverflow.in/3587/gate-it-2006-question-44

---

Make tree for every option and check heap property.

Is there any method other than the above mentioned?

edit: you dont even need to make a tree with enough practice

Answer 1

Answer: B

Answer 2

• Option (A) is wrong here because node $14$ comes after node $10$
• Option (B) is a correct representation of the max heap.
• Option (C) is wrong here because node $15$ comes after node $13$.
• Option (D) is wrong here because node $12$  comes after node $1$.

Note: Here we insert the given value one by one and check whether the value at root node $\geq$ to its children as a max heap, also it should be a complete binary tree. 

The max heap representation of option (B) is as follows:

Ref: some max heap insertion questions from the previous year:

• GATE CSE 2014 Set 2
• GATE CSE 2015 Set 3
• GATE CSE 1996
• GATE CSE 2005

Answer 3

Answer: B