23 votes 23 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? DS gatecse-2011 data-structures binary-heap easy + – go_editor asked Sep 29, 2014 • edited Jun 28, 2019 by Lakshman Bhaiya go_editor 8.1k views answer comment Share Follow See 1 comment See all 1 1 comment reply air1ankit commented Jan 18, 2018 reply Follow Share please edit the options..! 0 votes 0 votes Please log in or register to add a comment.
Best answer 24 votes 24 votes 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. ASHU2015 answered Dec 11, 2014 • edited Jun 29, 2019 by Arjun ASHU2015 comment Share Follow See all 3 Comments See all 3 3 Comments reply Peeyush Pandey commented Jan 10, 2019 reply Follow Share 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. 0 votes 0 votes Rajesh Panwar commented May 27, 2019 reply Follow Share 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. 1 votes 1 votes Kanwae Kan commented Sep 15, 2020 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
5 votes 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 Sankaranarayanan P.N answered Oct 4, 2014 Sankaranarayanan P.N comment Share Follow See all 0 reply Please log in or register to add a comment.