4.5k views
The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
retagged | 4.5k views
0
80 may be
+1
IT is 80
+1
+1

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
+2
ye toh bohot accha approach hei, i did mine in 3 cases and it came 80. awesome bro
+1
+2

How is it different than the answer answered by Anu007 on Feb 4?

0
How the formula Derived?
+1
I did not understand how you calculated. Please explain in detail.
+2

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}$

+1
+1
Yes, answer will be same @Warlock lord
+1
Great explanation

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

+2
this was my exact approach in d exam
0

I hope, Hence, 2*(2+2)=8 LINE SHOULD BE 2*(2*2)=8

0
wonderful answer sir :) easy to understand
f(1) = Number min heap with 1 node = 1
f(2) = Number min heap with 2 node = 1
f(3) = Number min heap with 3 node = 2    //swap left and right subtree

For a complete binary tree with n nodes number of nodes in left subtree (x) =
floor {((n-1)/2) + 1}.

1 node for Root (1 choice minimum valued node), x out of n-1 (leaving 1 for root) number of nodes in left subtree and n-1-x number of nodes in right subtree:
So, the number of arrangements possible:
Select root, Select and arrange x nodes in left subtree, arrange n-1-x nodes in right subtree
C(n-1, x)*f(x)*f(n-1-x)

Let number of arrangements are f(n):
f(n) = C(n-1, x)*f(x)*f(n-1-x)

Put n==7
f(7) = C(7-1, 3)*f(3)*f(7-1-3) = C(6,3)*f(3)*f(3) = 20*2*2 = 80
edited
0
Does this ensure that heap is a complete binary tree?
0
Already assumed the tree is CBT.
+1
Arrangements are nothing but filling numbers into a Complete Binary Tree.

Let's note down the facts first.
- The smallest element will be on the least level.
- The second smallest element will be on the first level.
- The third smallest element can be on the second or third level.

Root is fixed, the idea is to divide the building process into two subproblems, each solving both subtrees of the root.
Recurrence equation: T(n) = $_{k}^{n-1}\textrm{C}$ x T(k) x T(n-k-1), where k is number of nodes in left sub tree.

T(1) = 1

T(2) = 1, one root and one child.

T(3) = $_{1}^{2}\textrm{C}$ x T(1) x T(1) =  2

T(4) = $_{2}^{3}\textrm{C}$ x T(2) x T(1) =  3

T(5) = $_{3}^{4}\textrm{C}$ x T(3) x T(1) =  8

T(6) = $_{3}^{5}\textrm{C}$ x T(3) x T(2) =  20

T(7) = $_{3}^{6}\textrm{C}$ x T(3) x T(3) =  80

To put it down simply,  Among 7 elements, least element is fixed as root.
We are now left with 6 elements, the left subtree will have 3 elements, which can be picked in
$_{3}^{6}\textrm{C}$  x 2 ways.
Now we have 3 elements remaining and we can complete the heap in 2 ways only.
Hence $_{3}^{6}\textrm{C}$ x 2 x 2 = 80.

+1 vote
One more way to solve this problem could be  $^6C_3*2*2 = 80$
+1 vote

Minimum no of node in heap tree

My approach for this question