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. We will discuss the case clauses one by one. This will help us see how the concepts detailed before fit together. Here are the first two cases:

  def merge(ts1: List[Node], ts2: List[Node]): List[Node] = (ts1, ts2) match { 
    case (ts1, Nil) => ts1 
    case (Nil, ts2) => ts2 
    case (t1 :: ts11, t2 :: ts22) if (t1.rank < t2.rank) => t1 :: merge(ts11, ts2) 
    case (t1 :: ts11, t2 :: ts22) if (t2.rank < t1.rank) =&gt...