Learning Functional Data Structures and Algorithms

Binary number equivalence

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:

Merging

The insert method is a simplified case of the merge operation. ...