Alex is curious about data structures. He is working on binary trees recently and particularly interested in complete binary trees.
A complete binary tree satisfies that all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
A complete binary tree satisfies that all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
Alex defines his own complete binary tree: each node has a weight, while father's is always less than or equal to its sons'. He names this complete binary tree as minimum heap.
Now he wants to know: With N nodes weighted from 1 to N (each appears once), how many heaps can be created. The answer (represented by Q) may be very large, so please output a number P while P = Q mod M.
Followed Up:
Consider a complete binary tree of height n, where each edge is a one Ohm resistor. Suppose all the
leaves of the tree are tied together. Approximately how much is the effective resistance from the root to thisbunch of leaves for very large n?
(a) Exponential in n
(b) Cubic in n
(c) Linear in n
(d) Logarithmic in n
(e) Of the order square root of n
Followed Up:
Consider a complete binary tree of height n, where each edge is a one Ohm resistor. Suppose all the
leaves of the tree are tied together. Approximately how much is the effective resistance from the root to thisbunch of leaves for very large n?
(a) Exponential in n
(b) Cubic in n
(c) Linear in n
(d) Logarithmic in n
(e) Of the order square root of n
1 comment :
given N nodes an we know that its a complete binary tree so height would be h=log(N) where N is number of nodes.
now to calculate different type of heaps can be given by recurrence below :-
N(0) = 1
N(1) = 2
N(h)= 2*N(h-1)*N(h-2)
i not very sure abt the given recurrence , it may fail....
Post a Comment