GATE CSE 2011 | Question: 23

Question

A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

• A.        
• B.
• C.   
• D.

Comments

please edit the options..!

---

Option $(A)$ even not a Complete Binary Tree (CBT).

Answer 1

In option (A) - it is not a max heap because it is not a Complete Binary Tree (a heap must have all levels till last but one completely filled and in the last level all nodes must be filled from the left end without a gap till the last node)

In option (C) - it is complete binary tree but is not following the max heap property i.e. the value of parent node is not always greater than the child nodes as the node of value $5$ is less then one of its child node value of $8.$

In option (D) - similar to (C) option explanation here node of value $2$ is less than the child node value $4.$

Correct option is (B) and it satisfies all the properties of a max heap.

Comments

Without filling previous level completely we can not go to next level in heap, that is why a is wrong as it is not following the heap structure property.

---

in option (A) - it is not a max heap because it is not complete binary tree 
                     @ASHU2015 correct this line
it is not a max heap because it is not Almost Complete Binary tree. Because Heap Must Be Complete binary tree or almost complete binary tree.

---

Actually, it isn’t the heap property you’re talking about, it’s the property of the array on which heap is built upon, then you could actually use common ideas like,

$parent(x)=\lfloor\frac{i}{2}\rfloor \\ child(x)=2i,2i+1$

So, option A is right.

An afterthought, I would’ve definitely got it wrong in the exam.

Answer 2

heap is complete binary tree . so it is filled from top to bottom. left to right. option b is correct.

in option a even if all parents are greater , it does not follow heap structure