GATE CS 2018 Q.56 (CS Q.46): Binary Heaps and Priority Queues

The number of possible min-heaps containing each value from $\{1, 2, 3, 4, 5, 6, 7\}$ exactly once is _____.

Your answer

Official answer and solution

Official answer: 80
From: Official GATE 2018 answer key

Solution

Count valid min-heaps by recursively multiplying combination choices for subtree partition and recursive subtree arrangements.

A min-heap containing 7 distinct keys forms a complete binary tree of size 7, where the root has a left subtree of size 3 and a right subtree of size 3.

By the min-heap property, the smallest element (1) must be placed at the root.
The remaining 6 elements must be partitioned into 3 elements for the left subtree and 3 elements for the right subtree. The number of ways to choose elements for the left subtree is:

\binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20

For each subtree of 3 elements, the smallest of the 3 must be the root of that subtree. The other 2 elements can be placed as the left child and right child in $2! = 2$ ways.

Thus, the total number of valid min-heaps is:

N = \binom{6}{3} \times 2 \times 2 = 20 \times 4 = 80

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 56 of 65, printed as CS Q.46
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source