PriorityQueue in Scala

 1. Overview

The Scala programming language offers a wide variety of different collections. Besides the most common ones like Lists, Maps, and Sets, we also have Queues. In this tutorial, we’ll look at a specific type of Queue: the PriorityQueue.

2. What Is a Queue

Queues are useful collections for objects we want to process in a first-in-first-out (FIFO) order. They typically have two main operations:

• Add to the end of the queue
• Get the first (oldest) element of the queue

This collection allows us to process any kind of work in arriving order, by keeping all the information in memory. There may be cases where the amount of work and data needed to be kept in memory is so much that it won’t fit, and we should look for other solutions in those cases.

3. What Is a PriorityQueue

A PriorityQueue is a slightly more complex collection than the base Queue. It allows us to say that some items have a specific priority. This means that instead of an element always being added to the end of the queue, it may be added into any position, depending on other existing elements’ priority.

This is useful if we need to process many incoming tasks or objects, but when some of them may have higher priority (maybe our system has paid users whose requests should be answered faster).

3.1. PriorityQueue in Scala

The PriorityQueue class in Scala has two main methods:

• enqueue(), to add an element
• dequeue(), to remove the top element

These are the usual methods we see in normal Queues as well.

The other important detail about the Scala implementation is that it’s a mutable collection. This means that the collection is updated in place, with side effects, and we need to be more careful in concurrent code.

3.2. Initializing a PriorityQueue

Let’s put this in action and start by defining the PriorityQueue items in a case class:

scala> case class QueueItem(id: String, priority: Int)
defined class QueueItem

This is a simple object containing just a string identifier and a number for the priority (the higher the number, the higher the priority).

We also need to define the items’ ordering:

scala> def order(item: QueueItem) = item.priority
order: (item: QueueItem)Int

Now, let’s create our empty queue:

scala> import scala.collection.mutable.PriorityQueue
import scala.collection.mutable.PriorityQueue

scala> val q = PriorityQueue[QueueItem]()(Ordering.by(order))
q: scala.collection.mutable.PriorityQueue[QueueItem] = PriorityQueue()

Note that we pass the ordering function upon the queue creation. If we need to create many PriorityQueues in our application, this may become a boilerplate task. This can also lead to bugs if someone introduces a different and unexpected ordering.

This can be solved by passing an implicit ordering parameter:

scala> val q = PriorityQueue[QueueItem]()
<console>:14: error: No implicit Ordering defined for QueueItem.
       val q = PriorityQueue[QueueItem]()
                                       ^

scala> implicit val ord = Ordering.by(order)
ord: scala.math.Ordering[QueueItem] = scala.math.Ordering$$anon$5@1e9fd21d

scala> val q = PriorityQueue[QueueItem]()
q: scala.collection.mutable.PriorityQueue[QueueItem] = PriorityQueue()

As long as there’s an implicit ordering in scope, we don’t need to pass it every time.

3.3. Operating the PriorityQueue in Scala

Now, let’s add a few items with different priorities:

scala> q.enqueue(QueueItem("a", 2), QueueItem("b", 3), QueueItem("c", 1), QueueItem("d", 2))

And now, let’s try to use our newly populated PriorityQueue. But notice that according to the class documentation:

Only the dequeue() and dequeueAll() methods will return elements in priority order. Standard collection methods including drop(), iterator(), and toString() will remove or traverse the heap in whichever order seems most convenient.

Therefore, printing PriorityQueue won’t reveal the priority order of the elements, though the highest-priority element will be printed first. To print the elements in order, one must duplicate the PriorityQueue (by using clone(), for instance) and then dequeue them.

This means some naive approaches to printing the queue contents may be buggy, and we need to use the appropriate dequeue() and dequeueAll() methods to access the PriorityQueue elements if we want to access them based on the priority:

scala> q.toString
res2: String = PriorityQueue(QueueItem(b,3), QueueItem(a,2), QueueItem(c,1), QueueItem(d,2))

And we can see the priority wasn’t respected. So, we need to properly get the items:

scala> q.dequeueAll
res3: scala.collection.immutable.IndexedSeq[QueueItem] = Vector(QueueItem(b,3), QueueItem(d,2), QueueItem(a,2), QueueItem(c,1))

Using the dequeueAll() method, we get all items in the expected order.

4. Conclusion

In this article, we saw how to use a PriorityQueue to process elements according to their priority, using a simple implementation provided by the Scala standard library.