1.4k views

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?

1.
2.
in DS
edited | 1.4k views
0

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.

by (327 points)
edited by
0
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.
+1

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.

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
by Boss (11k points)

1
2