9 votes 9 votes The number of ways , in which numbers 1,2,3,4,5 can be inserted into binary heap,such that resultant binary heap is max heap ? given ans :8 Programming in C binary-heap algorithms + – minal asked Dec 9, 2016 minal 4.0k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply mohit chawla commented Dec 9, 2016 reply Follow Share should'nt it be 4?? 0 votes 0 votes minal commented Dec 9, 2016 reply Follow Share given is 8 , m getting 9 0 votes 0 votes smsubham commented Feb 18, 2018 i edited by smsubham Feb 18, 2018 reply Follow Share Total ways to arrange data is in 5 nodes is 5!. Divide it by 5 as we have 5 nodes in descendant in of root including itself. Similarity 3 in root left child as we have 3 descendant for it including itself. Formula: f(N) = C (N−1, L) * f(L) * f(R) Explanation: http://qa.geeksforgeeks.org/1970/qa.geeksforgeeks.org/1970/how-many-min-max-heaps-can-be-constructed-with-numbers-1-to-n Source : https://youtu.be/1U3loHkX5XE?t=2260 1 votes 1 votes Please log in or register to add a comment.
Best answer 10 votes 10 votes Yes, It is 8. [ Thanks @Kapil , @Sonam :) ] 1. 5, 4, 3, 2, 1 2. 5, 4, 3, 1, 2 3. 5, 3, 4, 2, 1 4. 5, 3, 4, 1, 2 5. 5, 4, 1, 2, 3 6. 5, 4, 1, 3, 2 7. 5, 4, 2, 3, 1 8. 5, 4, 2, 1, 3. vijaycs answered Dec 9, 2016 selected Dec 9, 2016 by Kapil vijaycs comment Share Follow See all 12 Comments See all 12 12 Comments reply minal commented Dec 9, 2016 reply Follow Share when 4 is 2nd node then 1,2,3 any can be any leaf right ..you missed that cases rt 1 votes 1 votes PEKKA commented Dec 9, 2016 reply Follow Share @vijaycs SIR is there any mathematical approch for the same question ? Like say if n nodes are to be inserted 0 votes 0 votes Kapil commented Dec 9, 2016 reply Follow Share @vijay 1 votes 1 votes sudsho commented Dec 9, 2016 reply Follow Share what if an array of 100 elements given? cant always go with hit n trail...there should be a generalised way keeping in mind height factor and how many will be in left subtree and how many in right 1 votes 1 votes srestha commented Dec 9, 2016 reply Follow Share Ans 8,rt? how 9?@Sonam 0 votes 0 votes Kapil commented Dec 9, 2016 reply Follow Share @sudsho Yes, what if 100 elements ? https://www.quora.com/How-many-Binary-heaps-can-be-made-from-N-distinct-elements This shows some generalization but I have never applied it. Should we try ? 0 votes 0 votes minal commented Dec 9, 2016 reply Follow Share i did with permutation which you considered but writing all cases ,.. but it will take time and if you miss any case then it will give wrong ans , i did like first fix 5 as root( 1 way) then , at 2nd level 3,4 node so there 2 cases 1) when 3 is 2nd node then 3rd node fixed 4 and other 2 nodes either 1,2 (2 ways) 2) when 4 is 2nd node then remainning nodes will pe arrange in 3! way = 6 ways so total 6+2+1 =9 , yes ans is 8 but where i am leaking ? 0 votes 0 votes minal commented Dec 9, 2016 reply Follow Share yes , given soln is same in test series. 0 votes 0 votes srestha commented Dec 9, 2016 reply Follow Share 5 fixed not a case here. until we go upto leaf , we cannot consider a way. 0 votes 0 votes minal commented Dec 9, 2016 reply Follow Share Ok... :) Keep in mind 0 votes 0 votes nehan commented May 24, 2017 reply Follow Share This is through Brute Force... Is there any formula? 0 votes 0 votes smsubham commented Feb 18, 2018 reply Follow Share @nehan Yes. check my comment on the ts on the question. 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes Answer wil be 8 only . First th will be fixed to the root . Now it is difficult to see from the internal nodes see from leaves. The remaining elements are (1,2,3,4). There will be 2 leaves possible. So possible pairs will be . if we choose (1,2) in leafs then the possiblity for its root is (3 or 4) . So 2 choices for root and 1,2 can also be arranged in 2 ways - total choices = 2*2 = 4 like wise (1,3) - 1 choice i.e 4. but arrangement of 1,3 or 3,1 possible - 2*1 choices - 2 (1,4 ) not possible (2,3) - 1 choice = 1*2 = 2 choices (2,4) not possible (3,4) not possible total ways = 4+2+2 = 8 choices Tendua answered Dec 9, 2016 Tendua comment Share Follow See 1 comment See all 1 1 comment reply minal commented Dec 9, 2016 reply Follow Share Thanks 0 votes 0 votes Please log in or register to add a comment.