The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
283 views
How many Binary Max-Heaps can be constructed from the elements {1,1,2,2,3,3,4,4} ?
asked in DS by Active (4.8k points) | 283 views
0
$\frac{8!}{8.4.3.2.1.1.1.1}=210$
0
But answer given is 44
0
here 4,4 cannot permuted
but 4,3 can be permuted as root of second highest subtree
but in case of 3,4 children also restricted
0

for (1,1) there will be 1 tree

for (2,2,1,1) there will be 2 trees

for (3,3,2,2,1,1) there will be 6 trees

for (4,4,3,3,2,2,1,1) there will be (4,4,3,3,2,2,1,1)

(4,4,3,2,3,2,1,1),(4,4,3,3,1,-,-,-),(4,4,3,1,3,-,-,-),(4,4,3,2,1,-,-,-),(4,4,3,1,2,-,-,-),(4,4,3,2,2,-,-,-)

Now also in 2nd highest level there are also 3 combinations

(4,3,4,-,-,-,-,-)

(4,4,2,-,-,-,-,-)

So, I think it will be more than 44

0
@ma'am i think question asks for possibilities of heap considering all elements together.
0
im getting 40

1 Answer

+6 votes

Possible max heaps are 44

So as we have 4 nodes , those can be arranged in 4! ways but 2 similar nodes are their (2,2 and 1,1)

so total number of ways =4!/2!*2!   =  6 ways  

Node 3 can be placed in 3 positions 

For 2,1,1 we have 3 nodes(positions) after placing Node 3 and they can be arranged in 3!/2! ways because we have similar node 1

So totally we have 3* 3!/2! = 9 ways 

If 1 is left child of 4 then other 1 must be child of node 1 as we cant place 2 or 3 in that position

So we have 3 positions

2,2,3 can be arranged in 3!/2!  = 3 ways    

Total possibilities =6+9+3 =18 ways

All these above ways can also be for this heap

6+9+3 ways   =18 ways 

In this we are left with 3 positions for 2,1,1 this can be arranged in 3!/2! =3 ways 

Same as above In this we are left with 3 positions for 2,1,1 this can be arranged in 3!/2! =3 ways 

generally as we have 3 positions and 2,1,1 is to placed we consider 3!/2! = 3 ways but 2 cant be child for 1 so we avoid this possibility then we are left with 2 ways   

By adding all these possibilities we get 18+18+3+3+2 =44 ways

answered by Boss (14.3k points)
edited by
0
ma'am in first figure 2nd part.. 3 can be paced in upper 3 positions so 3 possibility but why 2! . Doesn't it will be like this.. now we left with 2,1,1 so it will be 3!/2!
0
yes ur correct thank u let me change

in next one where 1 is left child of 4 then we have only 3 posibilities

Let me know if im wrong
+1
@shivani

why 4!/2! at first

elaborate more in words
+1
@sresta I tried to explain in detail you can check it now and let me know if anything wrong
0
I agree with u :)
0

Related questions

+5 votes
2 answers
3
asked Oct 26, 2016 in Algorithms by jenny101 Active (1.4k points) | 446 views
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
48,725 questions
52,831 answers
183,519 comments
68,656 users