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.

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 ...

Start Free Trial

No credit card required