How many different heaps are there for an array of a 6 entri

How many different heaps are there for an array of a) 6 entries? b) 12 entries? ) 18 entries? Explain your answer.

Solution

According to your requirement below is the equation through which you can calculate the different heaps for an array.

Equation:

L=2k11+min(2k1,M)

So, L=2k11+min(2k1,M)

And for Right Subtrees :

R=2k11+max(0,M2k1)

Returning to the original problem you can calculate number of entries for an array as the number of binary heaps with N distinct elements, as

f(0)=1f(0)=1
f(1)=1f(1)=1
f(N)=(N1L)f(L)f(R)