2 votes 2 votes The number of ways in which the numbers 1, 2, 3, 4, 5 can be inserted into binary heap. Such that resulted binary heap is max heap ________. DS binary-heap data-structures + – shivangi5 asked Nov 7, 2017 • reopened Jun 17, 2020 by Devwritt shivangi5 3.2k views answer comment Share Follow See all 15 Comments See all 15 15 Comments reply Show 12 previous comments Anu007 commented Nov 7, 2017 reply Follow Share Root node can be choosen as 5 since max heep Root Node has 3 left child and 1 right child. so from 4 number choose 3 number for left childs. 4c3= 4 ways fix one level 1 left child now you have 2 number you have to fill two child = 2 ways so total = 4 * 2 = 8 3 votes 3 votes Manu Thakur commented Dec 27, 2017 reply Follow Share "The number of ways in which the numbers 1, 2, 3, 4, 5 can be inserted into binary heap." answer will be 5! only for this original question. though if question is framed some other then answer may be 8. 0 votes 0 votes smsubham commented Feb 18, 2018 reply Follow Share Same question: https://gateoverflow.in/197327/datastructres 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes The answer is 8. 5 4 3 2 1 5 4 3 1 2 5 3 4 1 2 5 3 4 2 1 5 4 2 1 3 5 4 2 3 1 5 4 1 2 3 5 4 1 3 2 So total 8 ways. so the number of binary heaps with N distinct elements will be f(N) = C (N−1, L) * f(L) * f(R) See this: http://qa.geeksforgeeks.org/1970/qa.geeksforgeeks.org/1970/how-many-min-max-heaps-can-be-constructed-with-numbers-1-to-n Other Approach: https://gateoverflow.in/197327/datastructres smsubham answered Dec 27, 2017 • edited Feb 18, 2018 by smsubham smsubham comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 4 ways As we can choose one of the arrangement from 4,3 or 3,4 and 1,2 or 2,1 and 2,1 choose as a left subtree of the tree srestha answered Nov 7, 2017 srestha comment Share Follow See all 2 Comments See all 2 2 Comments reply smsubham commented Dec 27, 2017 reply Follow Share @srestha You have missed some cases. Please check my answer. 0 votes 0 votes Devwritt commented Jun 17, 2020 reply Follow Share correct answer is 8. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Try to think in this way.... we have to make max heap, so root element will be greatest among them and that is 5. 4 is one of child of 5(fixed), it can be left child or right child. if 4 is left child of root node of 5 then we left with 3 elements and can arrange in 3! ways= 6 ways and if 4 is right child, then left child will be 3 only of root node of 5. And then only 2 ways that we can arrange node 1 & 2. so total 6+2= 8 ways. Devwritt answered Jun 17, 2020 Devwritt comment Share Follow See all 0 reply Please log in or register to add a comment.