1 votes 1 votes Consider a binary min heap containing n elements and every node is having degree 2 ( i.e. full binary min heap tree). What is the probability of finding the largest element at the last level ? According to my understanding the largest element has to be a leaf and since leafs can be on two levels last and second last therefore the probability should be 1/2 DS data-structures binary-heap geeksforgeeks-test-series + – Pankaj Joshi asked Jan 14, 2017 • recategorized Jul 6, 2022 by Lakshman Bhaiya Pankaj Joshi 2.3k views answer comment Share Follow See all 19 Comments See all 19 19 Comments reply Nithish commented Jan 14, 2017 reply Follow Share yeah it must be 1 as, you can always find the largest element at the last level. 0 votes 0 votes vijaycs commented Jan 14, 2017 reply Follow Share doubt is genuine... if it was like- What is the probability of finding largest no in the leaf nodes then ans should have been definitely 1. But here it is said, last level... what if the last level contains only 2 nodes from left side or only 4 ...so on .. where total no of nodes = 100...then ...the largest element can also be there in the 2nd last level..right ?? = > It is also not said that all levels are full. 0 votes 0 votes Pankaj Joshi commented Jan 14, 2017 reply Follow Share consider this heap 4,5,10,6,7 largest element is on second last level 0 votes 0 votes air1 commented Jan 14, 2017 reply Follow Share Consider a binary min heap containing n elements and every node is having degree 2 ( i.e. full binary min heap tree). What is the probability of finding the largest element at the last level ? 0 votes 0 votes Pankaj Joshi commented Jan 15, 2017 reply Follow Share @air1 check my example every node does have degree 2 0 votes 0 votes air1 commented Jan 15, 2017 reply Follow Share was the highlighted part mentioned in the question or was it added by you? 0 votes 0 votes Pankaj Joshi commented Jan 15, 2017 reply Follow Share It was there already 0 votes 0 votes air1 commented Jan 15, 2017 reply Follow Share so the example you have given doesnt satisfy that constraint. you have to consider full binary trees only. (last level completely filled) 0 votes 0 votes Pankaj Joshi commented Jan 15, 2017 reply Follow Share They didn't define it that way that's what I'm saying just like you could define a complete binary tree differently everytime even different books follow different conventions 0 votes 0 votes air1 commented Jan 15, 2017 reply Follow Share please add some refrences where you find a definition different from this http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html 0 votes 0 votes Pankaj Joshi commented Jan 15, 2017 reply Follow Share in your own refrence a full binary tree is what I said it is don't just go with the one example given read the definition for further explanation check the wikipedia link in your own refrence 1 votes 1 votes air1 commented Jan 15, 2017 reply Follow Share yes you are correct. sorry about that. the picture on that page is deceiving. 1/2 seems correct. thanks for clearing this. 0 votes 0 votes IamRishabh commented Jan 19, 2017 reply Follow Share i guess in this answer would be : 1/2log(n) bcoz in min heap "max element" will be at last level so we have to traverse "log(n)"(height of heap) but it max element may be at right sub tree or left subtree so left =right decision makes it (0.5)log(n). correct me if i am wrong 0 votes 0 votes Rahul Jain25 commented Jan 19, 2017 reply Follow Share Answer is 1. It is given full binary min heap so it binary tree having maximum nodes, which gives answer 1. But they should have mentioned that non-leaf have degree 2 bcoz leaf will have degree 0. 0 votes 0 votes Pankaj Joshi commented Jan 19, 2017 reply Follow Share answer is half it has been explained above please read the comments 0 votes 0 votes IamRishabh commented Jan 19, 2017 reply Follow Share @rahul jain but in heap the order is of element i not fix at a given level so if max element is at right side and u choose left subtree then u won't get max element so how it could be "1" probability 0 votes 0 votes Rahul Jain25 commented Jan 19, 2017 reply Follow Share I have read all comments and you need to understand difference between full tree and complete tree. Question has given full tree you search on google about full tree. Answer is 1. And they have asked about level and not left or right subtree. So maximum is always at last level. 1 votes 1 votes Pankaj Joshi commented Jan 19, 2017 reply Follow Share https://en.wikipedia.org/wiki/Binary_tree 0 votes 0 votes joshi_nitish commented Jul 13, 2017 reply Follow Share @pankaj...since max can be present in last two levels, we can say that, P(last level)+P(second last level)=1, but how you are concluding that P(last level)=P(second last level) and hence P(last level)=1/2... it will depend on nos of leaves present in last level and second last level... 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes By Constructing a min Heap , we can say that the maximum element can be any where in the last level. There is not any possibility that any internal node contains the maximum element. So probability of getting maximum element at leaf level is 1. Arnab Bhadra answered Jun 20, 2017 Arnab Bhadra comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Dec 27, 2017 reply Follow Share Also, key values should be unique. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes there is ambigutiy... if leaf is in 2 levels than p=0.5 and if it is in last level p=1...that depends on value of n. nitish1995 answered Apr 5, 2017 nitish1995 comment Share Follow See all 0 reply Please log in or register to add a comment.