The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
4.5k views
The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
asked in Combinatory by Boss (18.3k points)
retagged by | 4.5k views
0
80 may be
+1
IT is 80
+1
+1
I got 72 as answer.

10 Answers

+22 votes
Best answer

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. 

answered by Veteran (61.2k points)
edited by
+2
ye toh bohot accha approach hei, i did mine in 3 cases and it came 80. awesome bro
+1
Please explain in detail
+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

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

answered by Boss (15.3k points)
+1
The answer remains same even if the question had asked max heap am I correct?
+1
Yes, answer will be same @Warlock lord
+1
Great explanation
+17 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

answered by Active (1.3k points)
+2
this was my exact approach in d exam
0

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

+16 votes

Answer : 80

answered by (187 points)
0
wonderful answer sir :) easy to understand
+4 votes
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
answered by Veteran (55.6k points)
edited by
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.
+4 votes

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.

answered by Active (3.1k points)
+1 vote
One more way to solve this problem could be  $^6C_3*2*2 = 80$
answered by Boss (11.8k points)
+1 vote
answered by Junior (507 points)
0 votes

Minimum no of node in heap tree

answered by (19 points)
0 votes

My approach for this question

answered by (273 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,240 questions
49,723 answers
163,933 comments
65,839 users