Counting the number of nodes in certain level binomial heap

Question

We have a binomial heap that consist of 2016 nodes.

Decompositing into binary we get

11111100000

THe heap consist of 6 strees with nodes 512 256 128 64 32 and 16.

But how can we calculate the number of nodes in certain level? What is the formula for calculating the number and what node are in for example 3 level?

Is ther any ultimate solution for this? Thanks

Answer 1

The term "binomial tree" comes from the fact that in a binomial tree of order n, given any integer 0 ≤ k ≤ n, there are exactly n choose k nodes in the binomial tree at that level. As you noted in your question, you can determine which trees will be present in the binomial heap by using the binary representation of the number in question. As a result, if you have a fast way of computing n choose k (either using a lookup table or some other method), you can determine how many nodes are at level k in the binomial heap by looking at the one bits set in n and, for each set 1 bit, computing the number of nodes in that individual tree, then summing the result together.