retagged by
38,652 views
67 votes
67 votes
The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
retagged by

14 Answers

Best answer
82 votes
82 votes

Lets answer this question in an easier way :

Now do $\frac{7!}{7 \times 3\times 3 }= 80$

Here $7!$ because $7$ items to be filled, Now $7$ because root has only $7$ nodes as its decedent including itself and only one can be the root. In same way we get $3$ and $3$ for the second level nodes and $1$ and $1$ for the third level. 

edited by
379 votes
379 votes

Ans: 80


Explanation:

Number of min-heaps possible with keys $\{1, 2, 3, 4, 5, 6, 7\}$.

A min-heap is a binary tree such that.

- the data contained in each node is less than (or equal to) the data in that node's children.

- the binary tree is complete. 

Since a binary heap is always a complete binary tree, so with $7$ nodes, we can have $2$ levels (root at level $0$). It's structure will be like this:

Now because of min-heap property, every node's value must be smaller than all of it's children. So, this ensure that the minimum will always be at the root. $\therefore$ $1$ will be at the root.

The second minimum element(i.e. $2$) can be present at the first level only(root is at the zeroth level). So we have two options. Let's, for now, fix $2$ at the left side.

We are now left with $5$ more elements $\{3, 4, 5, 6, 7\}$. For the left subtree's two leaves, we have $5 * 4$ ways. i.e. first choosing one of the 5 nodes, then choosing one of the remaining 4 nodes. 

Now $3$ nodes left. Out of these $3$, one will be the least among them, and that will definitely become the parent of the two remaining leaves(in the right subtree). Now with $2$ nodes left, we can arrange them in $2$ ways.

This gives $(5 * 4) * 2 = 40$ ways.

We can have the same number of ways, if we fixed $2$ at the right subtree instead of left. So total ways:

$= 40 * 2$

$= \mathbf{80}$

edited by
76 votes
76 votes

1 has to be root. Now,

case 1: 2 and 3 are on 2nd level.

so, 4,5,6 and 7 can occupy any of 4 positions in the 3rd level as all are less than 2 and 3. So, 4! arrangements. And 2 and 3 can be arranged in 2 ways in 2nd level (mirror image). Hence 2*24=48

case 2: 2 and 4 are on 2nd level

Now, 3 can only be below 2 and not 4 as it is MIN heap. So, 2 cases are possible 3XXX or X3XX, which gives 3!+3!=12 arrangements. And 2 and 4 can be arranged in 2 ways in 2nd level (mirror image). Hence 2*(6+6)=24

case 3: 2 and 5 are on 2nd level

Now, 3 and 4 can only be below 2 and not 5 as it is MIN heap. So, 2 arrangements are possible for 3 and 4 and similarly 2 for 6 and 7. And 2 and 5 can be arranged in 2 ways in 2nd level (mirror image). Hence, 2*(2+2)=8

Hence, total 48+24+8=80

62 votes
62 votes

Answer : 80

Answer:

Related questions