Question

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

Answer 1

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

Equation:

L=2k−1−1+min(2k−1,M)

So, L=2k−1−1+min(2k−1,M)

And for Right Subtrees :

R=2k−1−1+max(0,M−2k−1)

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)=(N−1L)f(L)f(R)