A binomial heap

A heap-ordered binomial tree is one in which every parent value is less than or equal to its children. In other words, a parent value is never greater than its children values.

Here's a diagram illustrating this:

The diagram shows a binomial heap with 13 nodes. All the binomial trees are linked together in increasing order of their ranks. This linked list of roots is the root list.

Let's start shaping up our code now.

Linking up

Our node is defined as a case class:

  case class Node(rank: Int, v: Int, children: List[Node]) 

The node holds the rank, the value v, and a list of children (possibly empty).

Given this definition, let's see how we could link two binomial trees. We always link trees of equal rank:

  def linkUp(t1: Node, t2: Node) = 
    if (t1.v <= t2.v) 
      Node(t1.rank+1, t1.v, t2 :: t1.children) 
    else 
      Node(t1.rank+1, t2.v, t1 :: t2.children) 

Here is the diagram showing linking up two trees of rank 0:

Let's grok this code with...