October 4, 2023
October 4, 2023
October 4, 2023
###### Nielit Scentist-B [02-12-2018]
October 4, 2023
 Question 9

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

 A 80 B 81 C 82 D 83
Question 9 Explanation:
–> We have 7 distinct integers {1,2,3,4,5,6,7} and sort it
–> After sorting, pick the minimum element and make it the root of the min heap.
–> So, there is only 1 way to make the root of the min heap.
–> Now we are left with 6 elements.
–> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80

Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .

Question 9 Explanation:
–> We have 7 distinct integers {1,2,3,4,5,6,7} and sort it
–> After sorting, pick the minimum element and make it the root of the min heap.
–> So, there is only 1 way to make the root of the min heap.
–> Now we are left with 6 elements.
–> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80

Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .