1,057 views
2 votes
2 votes
How many Binary Max-Heaps can be constructed from the elements {1,1,2,2,3,3,4,4} ?

1 Answer

7 votes
7 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

Related questions

0 votes
0 votes
0 answers
1
iarnav asked Jun 24, 2018
255 views
The number of possible min-heaps containing each value from {1,1,1,1,1,1,1} exactly once is _______This is a variance of Gate 2018 question and how will we deal if all va...
0 votes
0 votes
0 answers
2
Balaji Jegan asked Jun 17, 2018
220 views
What is the recurrence relation / math expression for the number of binary min heaps possible with "n" elements on which "k" elements are repeated "t" times where t=2 to ...
4 votes
4 votes
2 answers
3
jenny101 asked Oct 26, 2016
1,108 views
7 votes
7 votes
2 answers
4
Warlock lord asked Dec 5, 2017
1,112 views
From an array of size n , we need to find the k bigger elements. What is the data structure we should use to find k bigger element in best asymptotic complexity? 1.A max ...