🌞

# Purely functional Priority Queue

This is part of a series of articles on implementing various functional data structures in Scala. See other articles in this series:

In this part we will implement a basic Priority Queue in Scala. It will support the following operations efficiently:

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````abstract class PriorityQueue[A](implicit val ord: Ordering[A]) { // Add an item def +(x: A) : PriorityQueue[A] // Find min item def findMin: A // New Priority queue with min item deleted def deleteMin(): PriorityQueue[A] // Merges two PriorityQueue together def meld(that: PriorityQueue[A]) : PriorityQueue[A] } ``````

## Basics

There are different ways to implement a Priority Queue. We will use Binomial Heap. As usual we follow the approach from Okasaki. See this paper for details about implementing efficient and purely functional priority queues. We start with the basic implementation which is simple to understand. If you know how Binomial heaps work, skip to the next section. Else read on.

A Binomial heap is a forest of Binomial trees. A binomial tree of rank 0 has just a single node and of rank k (k > 0) has binomial trees of rank (0, 1, .. k-1) as its children. So it looks like (image from wikipedia): Another way to think about binomial tree is: to get binomial tree of rank k, take binomial tree of rank k-1 and insert another tree of rank k-1 as a child to the first tree's root. In any case, a Binomial heap of n elements would contain only trees of the above form and it will correspond to (k1, k2, ..kj) where k1k2..kj is the binary representation of n. So a heap of 5 (101) elements would have trees of rank 0 and 2. This means merging two binomial heap is similar to adding two binary numbers etc.

Ok, but how can we use a Binomial heap as a Priority Queue? Let's walk through an example and add the following items: (3, 5, 1, 2, 13, 15, 11, 12) in this order and see what we get: So you get the picture. Now to find the min element, we just need to walk through the roots of trees (`log(n)` items) and return the min. Adding an element is similar to adding 1 to a binary number and deletion is similar. Merging (aka melding) is like adding two binary numbers. In all operations all we need to make sure is that the root is properly selected (since that should always have the minimum).

## Implementation

Now that the idea is clear, let's start writing some code. We have a concrete class `BinomialQueue` to represent the queue and a `Node` class to represent individual trees. Let's look at the `Node` class first:

 ``````1 2 3 4 5 6 7 8 9 `````` ``````case class Node[A](data: A, rank: Int = 0, children: List[Node[A]] = Nil) (implicit val ord: Ordering[A]) extends Ordered[Node[A]] { def link(other: Node[A]) = if (ord.compare(data, other.data) < 0) Node(data, rank+1, other :: children) else Node(other.data, other.rank+1, this :: other.children) override def compare(that: Node[A]): Int = ord.compare(data, that.data) } ``````

For simplicity, every `Node` stores its rank and have data and list of children. It is ordered based on the data (which needs to have an implicit `Ordering`). Other than this we have a `link` method which links two `Node` together keeping the min element as new root. For example, in the above figure, when we insert `2`, we link `[1,2]` and `[3,5]` together and `1` gets to be the root.

Now we can define the `BinomialQueue` class:

 ``````1 2 3 4 `````` ``````private final case class BinomialQueue[A] (nodes: List[Node[A]]) (implicit override val ord: Ordering[A]) extends PriorityQueue[A] { } ``````

## Operations

#### Insert

 ``````1 2 3 4 5 6 7 8 `````` ``````def +(x: A) : BinomialQueue[A] = BinomialQueue(insertNode(Node(x), nodes)) private def insertNode[T](n: Node[T], lst: List[Node[T]]) : List[Node[T]] = lst match { case Nil => List(n) case x :: xs => if (n.rank < x.rank) n :: x :: xs else insertNode(x.link(n), xs) } ``````

We have 3 case to handle. Inserting to:

• Empty heap : Create a new List having a rank-0 Node (Eg. inserting 3 above)
• Heap without a rank-0 node: Just add a rank-0 Node to our list (Eg. inserting 1, 13 etc above)
• Heap with a rank-0 Node: Now we need to merge and recursively insert merged Node (Eg. inserting 5, 2 etc)

#### Find Minimum

Just returns the `Node` with min element.

 ``````1 `````` ``````def findMin: A = nodes.min.data ``````

#### Merge

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````def meld(that: PriorityQueue[A]) : PriorityQueue[A] = BinomialQueue(meldLists(this.nodes, that.nodes)) private def meldLists[T](q1: List[Node[T]], q2: List[Node[T]]) : List[Node[T]] = (q1, q2) match { case (Nil, q) => q case (q, Nil) => q case (x :: xs, y :: ys) => if (x.rank < y.rank) x :: meldLists(xs, y :: ys) else if (x.rank > y.rank) y :: meldLists(x :: xs, ys) else insertNode(x.link(y), meldLists(xs, ys)) } ``````

Logic is similar to insert: If a particular ranked node does not exist on one list we can just copy it to output. Same ranked Nodes are merged via linking them together.

### Delete Minimum

 ``````1 2 3 4 `````` ``````def deleteMin(): PriorityQueue[A] = { val minNode = nodes.min BinomialQueue(meldLists(nodes.filter(_ != minNode), minNode.children.reverse)) } ``````

Finds the min Node and removes it. The children of a Binary tree conveniently forms a Binary heap in reversed order, so we just merge that to other Nodes.

We are done and have a working Priority Queue implementation (we could make some operations more efficient by using Skew binary heaps, but thats for a later time). However, the other common operations on collections like iterating, map, filter etc are missing. Scala has a rich collections library and it is not difficult to reuse most of it for a new collection object. See this excellent guide to understand the design of Scala collections and how to adapt your collection to use it.

In a nutshell we need to do two things: Provide a way to iterate over the items (`Traversable` or `Iterable`) and a way to build a new collection (`Builder`). There are also higher level of abstractions that make things easier. So we change the `PriorityQueue` definition as follows:

 ``````1 2 3 4 `````` ``````abstract class PriorityQueue[A](implicit val ord: Ordering[A]) extends Iterable[A] with GenericOrderedTraversableTemplate[A, PriorityQueue] with IterableLike[A, PriorityQueue[A]] { ``````

That's quite a mouthfull, so let's take it one by one. Iterable just defines an `iterator` method which yields elements of the collection in some order and an `isEmpty` method. We can implement it as follows:

 ``````1 2 3 4 5 6 7 `````` ``````override def isEmpty: Boolean = nodes.isEmpty //Inside BinomialHeap override def iterator: Iterator[A] = nodes.flatMap(_.toList).iterator //Inside Node: def toList : List[A] = data :: children.flatMap(_.toList) ``````

`IterableLike` is for ensuring the same-result-type principle. GenericOrderedTraversableTemplate is an easy way to define the builder using a companion object for ordered collections. It has following methods to be implemented:

 ``````1 2 3 `````` ``````override def orderedCompanion: GenericOrderedCompanion[PriorityQueue] = PriorityQueue override protected[this] def newBuilder: mutable.Builder[A, PriorityQueue[A]] = PriorityQueue.newBuilder ``````

Basically we just need to tell which is the companion object where the builder is specified. Finally we need to define the companion object which defines how to build a `BinomialQueue` from other collections:

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````object PriorityQueue extends OrderedTraversableFactory[PriorityQueue] { override def newBuilder[A](implicit ord: Ordering[A]): mutable.Builder[A, PriorityQueue[A]] = new ArrayBuffer[A] mapResult { xs => xs.foldLeft(BinomialQueue[A](Nil))((t, x) => t + x) } implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, PriorityQueue[A]] = new GenericCanBuildFrom[A] } ``````

Now we can use all the power of Scala collections.

 ``````1 2 3 4 5 `````` ``````val pq = PriorityQueue(1,2,3,4,5,6) // BinomialQueue(5, 6, 1, 3, 4, 2) pq map (_ * 2) filter (_ < 6) // BinomialQueue(2, 4) val sq = PriorityQueue("a", "aa", "aaaaa") // BinomialQueue(aaaaa, a, aa) sq map (_.length) reduce (_*_) // 10 ``````

Isn't that cool?

You can find the complete code here. The Binomial heap images were generated using this code. That's all for now, see you later!