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 Show 9 previous comments 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.