If you want to make money online : Register now

How many different heaps are there of a given shape?

, , No Comments
Problem Detail: 

Let's say we have a tree like this:

enter image description here

Suppose we are given $N$ distinct elements, $N$ being the number of vertices in the tree (in this case, $N=13$).

In how many ways can we distribute the given $N$ elements in the tree so that it has the max-heap property (any vertex is larger than its children)?

Asked By : Vlad
Answered By : Yuval Filmus

You can compute this recursively as follows. It will be convenient to denote (binary) trees using the following notation: a tree is either a leaf $\ast$ or is formed from two subtrees $(T_1,T_2)$. For a tree $T$, let $|T|$ denote the number of vertices in $T$, defined inductively by $|\ast|=1$ and $|(T_1,T_2)| = |T_1|+|T_2|+1$. Finally, let $N(T)$ denote the number of ways of allocating the integers $1,\ldots,|T|$ to $T$ so that the max-heap property is satisfied.

The base case is $N(\ast)=1$. Now consider a tree $T=(T_1,T_2)$. Clearly we must put $|T|$ at the root. Every filling out of the rest of the tree can be described as follows:

  • Choosing a set $S_1$ of integers as labels for $T_1$. The other elements $S_2$ function as labels for $T_2$.
  • Arranging $S_1$ in $T_1$ in a way satisfying the max-heap property.
  • Same for $S_2$ and $T_2$.

The number of ways of accomplishing the second bullet is $N(|T_1|)$, and the number of ways of accomplishing the third bullet is $N(|T_2|)$; in both cases, the exact contents of $S_1$ and $S_2$ are not important. The number of choices in the first bullet is $\binom{|T|-1}{|T_1|}$, and we conclude that $$ N((T_1,T_2)) = \binom{|T_1|+|T_2|}{|T_1|}N(T_1)N(T_2), $$ with initial case $N(\ast) = 1$.

Using this formula you can easily compute that for your tree the number of possibilities is $304128$ (I believe).

You can also "unroll" the formula: $$ N(T) = \prod_{x=(x_1,x_2) \in T} \binom{|x_1|+|x_2|}{|x_1|}, $$ where $x$ goes over all internal nodes in $T$. For example, for your tree we get (top to bottom, left to right) $$ \binom{12}{5} \binom{4}{3} \binom{6}{5} \binom{2}{1} \binom{4}{1} \binom{2}{1} = 304128. $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53490

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback