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 Rishabh Gupta 2 commented Nov 7, 2017 reply Follow Share number of ways to insert = 5! 0 votes 0 votes shivangi5 commented Nov 7, 2017 reply Follow Share Ans given is 8 0 votes 0 votes Anu007 commented Nov 7, 2017 i edited by Anu007 Nov 7, 2017 reply Follow Share No it will be $\frac{5!}{5 $\times$ 3}$ = 8 0 votes 0 votes srestha commented Nov 7, 2017 reply Follow Share why 5! 4 ways I think 0 votes 0 votes shivangi5 commented Nov 7, 2017 reply Follow Share Why 5!/6 @ Anu007 0 votes 0 votes Rishabh Gupta 2 commented Nov 7, 2017 reply Follow Share @shivangi5 5 4 1 2 3 5 4 1 3 2 5 4 2 3 1 5 4 2 1 3 5 4 3 1 2 5 4 3 2 1 5 3 4 1 2 5 3 4 2 1 The question is a bit misleading. It should not ask for number of ways to insert into a heap. But rather, the number of ways these 5 numbers can be saved in an array such that the resulting array is a max-heap. 5 votes 5 votes Anu007 commented Nov 7, 2017 reply Follow Share sorry it was 8 . 0 votes 0 votes srestha commented Nov 7, 2017 reply Follow Share yes better to write every arrangement 0 votes 0 votes Anu007 commented Nov 7, 2017 reply Follow Share i dont think so it is ambigous. Max tree with 5 nodes has some predifined structure i,e, complete binary tree . now we have to fill with 5 numbers as given , 0 votes 0 votes Rishabh Gupta 2 commented Nov 7, 2017 reply Follow Share @sreshtha I said 5! because I thought that it is already a heap, and whenever we will insert an element we will apply heapify. So I thought that in whatever order we insert, the result will be a heap. total possible orders = 5! :) 1 votes 1 votes Anu007 commented Nov 7, 2017 reply Follow Share if they give 1 to 10 number then you may not able to write all possobility . here some logic is used. 0 votes 0 votes shivangi5 commented Nov 7, 2017 reply Follow Share @Anu007 could you please elaborate why are you doing like 5!/5*3 0 votes 0 votes 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.