Max Heap

Question

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 ________.

Comments

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. ⁴c₃= 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

---

"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.

---

Same question: https://gateoverflow.in/197327/datastructres

Answer 1

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

Answer 2

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

Comments

@srestha

You have missed some cases. Please check my answer.

---

correct answer is 8.

Answer 3

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.