max heap

Question

The number of distinct max heap are possible with keys 1, 2, 3, 4, 5 are

Comments

$\binom{4}{3}$ * 2 * 1 = 8.

Root will be 5. The left subtree will be having 3 elements and 1 element in the right subtree. The no. of ways choosing 3 elements among the 4 elements is $\binom{4}{3}$. With 3 elements we will be having 2 max heap.

https://gateoverflow.in/91131/max-heap

---

@Hemant Parihar .. I got 8 but I had to draw all possible cases.. is there any method to calculate? because for more no. of nodes it would become difficult to keep track..

---

@mini panda, Yes there is a recurrence relation on the no. of min/max heap with distinct N keys.

See here.

https://www.quora.com/How-many-Binary-heaps-can-be-made-from-N-distinct-elements

https://gateoverflow.in/102171/min-heap

---

Thank you..the 2nd link was more helpful :D