There is a surprising equivalent in the processes of binomial heap insertion and incrementing a binary number. For example, the following figure shows the addition of
1 to a number, say
6, and the equivalent tree insertion into a binomial heap:
The binary addition happens from right to left, whereas binomial insertion happens from left to right. Also, the link up triggers changes to the heap similar to the way the carry triggers further changes to the number:
insert method is a simplified case of the
merge operation. ...