GATE 2018 CS Q.46: solution and answer

GATE 2018 · CSQ.46 · 2 marks · NAT

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The number of possible min-heaps on {1,2,...,7} is 80.

Official answer: 80Source: Official answer key, GATE 2018 CS (IIT Guwahati)

The heap shape for 7 distinct elements is a fixed complete binary tree: a root with a left subtree of 3 nodes and a right subtree of 3 nodes (since (7-1)/2 = 3 each), and each 3-node subtree is itself a root with two leaf children.
In any min-heap, the smallest of the 7 values (namely 1) must sit at the root, and each subtree must independently be a valid min-heap on its own set of elements.
Choose which 3 of the remaining 6 elements {2,3,4,5,6,7} occupy the left subtree (the other 3 automatically go to the right subtree): $(3 6) = 20$ ways.
For a 3-element subtree (root + 2 leaf children), the minimum of those 3 elements is forced into the subtree's root position; the other two elements can be placed into the two leaf positions in either order, since the min-heap property only requires parent ≤ child and imposes no ordering between the two children. This gives $2$ valid arrangements per 3-element subtree.
The left and right subtree arrangements are chosen independently, giving $2$ ways for the left subtree and $2$ ways for the right subtree.
Total number of distinct min-heaps = (ways to split the 6 non-root elements) × (left subtree arrangements) × (right subtree arrangements) = $20 \times 2 \times 2 = 80$ .
This agrees with Knuth's general heap-count formula $n! / \prod (subtree sizes) = 7! / (7 \times 3 \times 3 \times 1 \times 1 \times 1 \times 1) = 5040/63 = 80$ , confirming the answer.
Final answer: 80.

KEY IDEA

A heap on n distinct keys is stored in the unique shape of a complete binary tree; the number of distinct heap arrangements equals n! divided by the product of the sizes of every subtree (Knuth's formula), because each subtree's elements can be permuted internally in "subtree-size!" ways relative to the constraint that only the minimum of each subtree must sit at that subtree's root.

WATCH OUT FOR

Treating the two children of a 3-node subtree as distinguishable in a way that forces extra constraints (e.g., assuming a fixed left<right order), which wrongly gives 1 arrangement per 3-node subtree instead of 2, or forgetting to multiply by the C(6,3) way of splitting the remaining 6 keys between the two subtrees.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

GATE 2018 CS Q.46: solution and answer

Answer and solution

More Trees & heaps questions