The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
605 views

Number of Max_heap possible ?

asked in DS by Active (1k points) 1 flag | 605 views
0
0
It does not have explanation. I know answer i need explanation.

1 Answer

+3 votes
Best answer

Given Elements : 12,10,8,5,3,2,1,7,9

1) Maximum of all these will be root i.e. Root = 12 ---->1 way --->(1)

2) Remaining : 8 elements

Out of 8 choose 5 for left subtree in 8C5 ways and 3 for right subtree in 3C3 ways. --->(2)

3)Left Subtree :

Out of 5, maximum element is the root.

Out of remaining four , choose 3 for left subtree in 4C3 ways , Out of 3 elements chosen, max is root and rest 2 can be in any of the 2 leaf nodes.

#Heaps possible in Left Subtree= 4C3 * 2 --->(3)

3)Right Subtree :

Out of 3, maximum is root.

Remaining 2 elements can be arranged in 2 leaves in 2 ways.

#Heaps possible in Right Subtree=  2 --->(4)

Hence From (1) to (4) , Total # heaps possible = 1 * ( 8C5 * 4C3 *2 )  * (3C3 * 2 )

=56 * 4 * 2 * 2 =896 (ANS)

answered by Active (1k points)

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

47,005 questions
51,325 answers
177,500 comments
66,668 users