recategorized by
2,068 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.

Related questions

0 votes
0 votes
1 answer
1
syedasafoora asked Nov 8, 2023
221 views
Consider the following algorithm for Build-Max-heap and the given array A=[ 47,96, 35, 54, 77, 65, 83]. Run this algorithm on the given array and redraw the heap and the ...
0 votes
0 votes
1 answer
2
amitarp818 asked Nov 28, 2023
564 views
Consider the following array of elements<96,42,50,17,15,5,7,11,39,23,6,9,19,100,12>The minimum number of interchanges using buildheap needed to convert it into a max heap...