The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6,…
2018
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _____.
Attempted by 97 students.
Show answer & explanation
Correct answer: 80
Key idea: count heaps by placing the smallest element at the root and distributing the remaining elements between the left and right subtrees.
For n distinct keys, the number of min-heaps H(n) satisfies the recurrence H(n) = C(n-1, L) × H(L) × H(R), where L is the number of nodes in the left subtree (determined by the complete binary tree shape) and R = n-1-L.
For n = 7 the heap is a perfect binary tree, so L = 3 and R = 3.
Compute H(3): H(3) = C(2,1) × H(1) × H(1) = 2 × 1 × 1 = 2.
Then H(7) = C(6,3) × H(3) × H(3) = 20 × 2 × 2 = 80.
Answer: 80.
A video solution is available for this question — log in and enroll to watch it.