GATE CS 2018 Q46 — Binary Heaps

A min-heap containing $n$ distinct elements is a complete binary tree where the root always contains the minimum element. The remaining $n-1$ elements are distributed between the left subtree of size $L$ and the right subtree of size $R$ ($L + R = n - 1$).

The number of ways to construct a min-heap of size $n$, denoted as $N(n)$, is given by the recurrence relation:

For $n = 7$, a complete binary tree has a left subtree of size $L = 3$ and a right subtree of size $R = 3$.

1. Calculate $N(3)$: For a heap of size 3, the left and right subtrees each have size 1 ($L=1, R=1$). $$N(3) = \binom{2}{1} \times N(1) \times N(1) = 2 \times 1 \times 1 = 2$$
2. Calculate $N(7)$: Using $N(3) = 2$: $$N(7) = \binom{6}{3} \times N(3) \times N(3) = 20 \times 2 \times 2 = 80$$

Thus, the number of possible min-heaps is 80.