The number of binomial trees in a binomial heap

Question

I keep finding online that the number of binomial trees in a binomial heap of $n$ nodes is $\lfloor \log_2 n + 1 \rfloor$, however I can't seem to prove it. I know that the total number of nodes, $n$, is the sum of 2 power terms which are all unique but I can't seem to derive the desired value of $\lfloor \log_2 n + 1 \rfloor$.

Any help would greatly be appreciated, thanks!

Answer 1

First of all, the number of binomial trees in a binomial heap having $n$ nodes is at most $1 + \lfloor \log_2 n \rfloor$. To prove this, we use the following properties:

1. In a binomial tree of order $k \geq 0$, there are exactly $2^k$ nodes.
2. In a binomial heap, there can be at most one binomial tree of each order.

Let our binomial heap have $n \geq 1$ nodes and $k$ binomial trees of orer $o_i$, where $1 \leq i \leq k$ and $o_i \geq 0$. The second property guarantees that $o_i$ are distinct. The first property tells that $i$-th binomial tree has exactly $2^{o_i}$ nodes. As a result, we get

$$ n = \sum_{i=1}^{k} 2^{o_i} $$

which is nothing but binary representation of $n$. So, $k$ is same as the number of 1-bits in binary representation of $n$. It is well known that it takes exactly $1 + \lfloor \log_2 n \rfloor$ bits to represent $n$ in binary. Hence, $k \leq 1 + \lfloor \log_2 n \rfloor$.

For example, $ (13)_{10} = (1101)_{2}$. So a binomial heap with 13 nodes will have 3 binomial trees, which is at most 4 (= number of bits in 13).