O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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:

A binomial heap

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required