Ans: 80
Explanation:
Number of min-heaps possible with keys $\{1, 2, 3, 4, 5, 6, 7\}$.
A min-heap is a binary tree such that.
- the data contained in each node is less than (or equal to) the data in that node's children.
- the binary tree is complete.
Since a binary heap is always a complete binary tree, so with $7$ nodes, we can have $2$ levels (root at level $0$). It's structure will be like this:
Now because of min-heap property, every node's value must be smaller than all of it's children. So, this ensure that the minimum will always be at the root. $\therefore$ $1$ will be at the root.
The second minimum element(i.e. $2$) can be present at the first level only(root is at the zeroth level). So we have two options. Let's, for now, fix $2$ at the left side.
We are now left with $5$ more elements $\{3, 4, 5, 6, 7\}$. For the left subtree's two leaves, we have $5 * 4$ ways. i.e. first choosing one of the 5 nodes, then choosing one of the remaining 4 nodes.
Now $3$ nodes left. Out of these $3$, one will be the least among them, and that will definitely become the parent of the two remaining leaves(in the right subtree). Now with $2$ nodes left, we can arrange them in $2$ ways.
This gives $(5 * 4) * 2 = 40$ ways.
We can have the same number of ways, if we fixed $2$ at the right subtree instead of left. So total ways:
$= 40 * 2$
$= \mathbf{80}$
