What are elements of dramatic representation?

The relationship between a binomial heap with n elements and the binary representation of n, is that each of the trees in the binomial heap correspond to a digit in the binary representation of the total number of nodes used to create the binomial heap. Is this relationship merely a coincidence?

• Answer:

  This is absolutely not a coincidence. A binomial heap behaves very much like a binary number. A tree with 2^k contributes 2^k to the total number of nodes, just as a 1 in the kth place in a binary number contributes 2^k to the total of that number. I think the connection becomes really clear when you start doing operations on the binomial heap and we see how they correspond to operations on binary numbers. Let's do an example. Consider what happens when we add 1 to a binary number using the standard addition operation. First we add the digit 1 to the 1's place:  1100111 +           1 --------------  1100112 and then we carry:  1100120 -->  1100200 -->  1101000 Okay, now what happens when we insert an element into a binomial heap? Suppose we have a binomial heap with 103 elements (corresponding to the binary number 1100111). This binomial heap has trees of size 1, 2, 4, 32, and 64 (one tree for each '1' digit in the binary representation of the number of elements!) When we insert an element into this tree, we merge it with the size-1 tree to get a size-2 tree. We then merge that tree with the original size-2 tree; this gives a size-4 tree. Then again we merge that tree with the original size-4 heap; this gives us a size 8 tree. Now we are left with heaps of size 8, 32, and 64. Binary number 1101000. See the connection? Each operation of merging two heaps corresponded to one of the carry operations we made in the simple addition exercise above! When we merge two binomial heaps, the merging operations that you do on the trees look like the carries you will do in the addition of two binary numbers, each one corresponding to the number of elements in each heap. So, no, it's not a coincidence. There's a very good reason why the binomial heap looks like a binary number. And in fact, the operations you do on the binomial heap looks just like the elementary addition algorithms you learned as a kid, on the binary numbers.