GATE Overflow Test Series | Mock GATE | Test 2 | Question: 46

Question

The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7,8\}$ exactly once is __________

Answer 1

We need $4$ levels for $8$ nodes in a min-heap. This means one sub-tree of root will have $4$ nodes and other one $3$ nodes.
Now, number of min-heaps with $4$ nodes $=3$  and that with $3$ nodes $ = 2.$
Since $4!/3 = 8$ and $3!/2 = 3$ to find the number of min-heaps with $8$ nodes we can divide $8!$ first with $8$ -- since root is fixed instead of having $8$ ways and then by $8$ and $3.$
Thus, number of min-heaps with $8$ nodes $ = \dfrac{8!}{8.8.3} = \dfrac{7!}{24} = 210$
Reference: https://cs.stackexchange.com/questions/6456/how-many-different-max-heaps-exist-for-a-list-of-n-integers

Comments

Can we please get a detailed explanation?

Like something with visuals and description as to why did you divide 4! by 3 and similarly, 8!/8?

Answer 2

root will take the smallest one.so remaining element are 7.

now lets consider the right subtree which have 3 nodes,here possibilities are 7C3 * 2.

now we have 4 keys in our hand,out of that the smallest one will go to root of left subtree.remaining are 3 nodes.

3C1 for right child of left subtree of node.

remaing 2 elements have only one choice as the largest among them will go to last level node & remaing is top of that.

7C3 * 2 * 3C1 = 210

Comments

@mrinmoyh , yes.

$T(8)= 7C_{3}*$$T(4)*T(3)$                  this means, after fixing root node, we can choose 3 out of 7 remaining nodes for right subtree and solve right subtree in T(3) and solve left subtree in T(4). This can be solved recursively to get 210

---

@mrinmoyh can you please tell me how right subtree have possibility 7C3 *2 

i get that it can be 7C3 but why multiply with 2

---

If there are n elements, then one of the element is always root depending upon minheap and maxheap.

Rest (n-1) element will be the part of subtree.

Divide these elements such that n₁ + n₂ = n-1, here n₁ and n₂  are the number of elements in left and right subtree.

T(n) = ^(n-1)C_n1 * T(n1) * T(n2)..............Recursive function 

and T(1) = T(2) = 1