Given the integers from 1 to n, determine how many valid binary heaps can be constructed with these numbers.
Example: 1 2 3 4
valid min heaps are: {1 2 3 4}
, {1 3 2 4}
, {1 2 4 3}
,
Thus the answer is 3
hint:
A binary heap has a predefined number of nodes, and a well defined structure (Complete tree)
Think recursively about this problem.
"Chose" which of the non-root numbers go to the left subtree, and which to the right - and recursively invoke on the subtrees.
f(1) = 1 //no sons
f(2) = f(1) * 1 //one son and a root
//chose which element will go to the left sub-tree, and recursively invoke.
f(3) = Chose(2,1)* f(1) * f(1) * 1
f(4) = Chose(3,2)*f(2) * f(1) * 1 //chose which 2 elements will go to the left sub tree
...
The question is tagged as homework, so I am leaving finding the exact numbers for the general case up to you.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With