The Gateway to Computer Science Excellence
+17 votes

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?

in DS by Veteran (106k points)
edited by | 1.6k views
please edit the options..!

2 Answers

+22 votes
Best answer

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
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.

+5 votes
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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,834 questions
57,786 answers
108,214 users