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

number of ways to insert = 5!

---

Ans given is 8

---

No it will be $\frac{5!}{5 $\times$ 3}$ = 8

---

why 5!

4 ways I think

---

Why 5!/6 @ Anu007

---

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

---

sorry it was 8 .

---

yes better to write every arrangement

---

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 ,

---

@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! :)

---

if they give 1 to 10 number then you may not able to write all possobility .

here some logic is used.

---

@Anu007 could you please elaborate why are you doing like 5!/5*3

---

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.