Register

Number of max heaps

• recategorized by
2,131 views

1 Answer

2 votes
2 votes

Number of different max heap possible using n distinct keys is given by recurrence relation
$T(n) = {n-1 \choose l}*f(l)*f(r)$, where $l$ is number of nodes in left sub-tree.
Number of max heap possible with 1 key is 1 therefore $T(1) = 1$

Similarly number of max heap possible with 2 key is also 1, $T(2) = 1$

$T(3) = {2 \choose 1} *T(1)*T(1) = 2*1*1 = 2$

$T(4) = {3 \choose 2}*T(2)*T(1) = 3*1*1 = 3$

$T(5) = {4 \choose 3}*T(3)*T(1) = 4*2*1 = 8$

Therefore ans is 8.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
0 answers
2
Balaji Jegan asked Jun 4, 2018
1,086 views
Number of Max Heap
How many max-heaps can be formed with the following elements? $\{1,1,1,2,2,2,3,3,3,4,4,4\}$
How many max-heaps can be formed with the following elements?$\{1,1,1,2,2,2,3,3,3,4,4,4\}$
User Avatar
0 votes
0 votes
0 answers
3
iarnav asked Jun 24, 2018
267 views
#DS Min Heaps Possible?
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 values are same?
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...
User Avatar
1 votes
1 votes
1 answer
4
iarnav asked Jun 21, 2018
473 views
#DataStructure Heaps Self Doubt.
In a binary Heap of 100 elements time taken to find the 99th element? or in a binary heap on "n" elements, time taken to find (n-1)th element? Note ; I'm not asking about smallest or largest, but simply the 99th element.
In a binary Heap of 100 elements time taken to find the 99th element?or in a binary heap on "n" elements, time taken to find (n-1)th element? Note ; I'm not asking about ...
User Avatar
Link Copied!