In many algorithms—including Dijkstra’s algorithm for finding the shortest path between two vertices in a weighted graph—we need access to a data structure that maps elements to numbers or priorities where we can efficiently obtain and remove the element(s) with the least priority and add new elements as the algorithm progresses. Such a data structure is usually called a priority queue and often implemented using a heap. While a heap implementation is very efficient, it has the drawback that some operations—such as determining the priority of an arbitrary element or finding the element with the greatest priority—still require linear time. Moreover, heaps are inherently mutable and therefore not thread-safe.

In functional programming, we usually prefer immutable (persistent) data structures where every update results in a new version of the data structure with the old version still accessible. For Clojure, Mark Engelberg has created an implementation of what he calls a priority map, which is an immutable data structure that combines the functionality of priority queues with the fast lookup functionality of maps. Alternatively, priority maps can be viewed as regular maps but with entries sorted by value, so iterating over a priority map produces key-value pairs with ascending values. In Scala, another functional programming language for the JVM, we have immutable maps and immutable sorted maps, where entries are sorted by keys, but no immutable map-like data structure where entries are sorted by value.

Without further ado, I present to you scala-prioritymap, which is an implementation of immutable priority maps in Scala and fully compatible with the Scala collections API. As such, priority maps extend the Map trait, and any operation that is defined on maps also works on priority maps, but they respect the (implicit) ordering on values.

scala> import de.ummels.prioritymap._
import de.ummels.prioritymap._

scala> val m = PriorityMap('a' -> 1, 'b' -> 2, 'c' -> 0)
m: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(c -> 0, a -> 1, b -> 2)

scala> m.toSeq
res1: Seq[(Char, Int)] = ArrayBuffer((c,0), (a,1), (b,2))

If there is no implicit ordering defined for your value type or you want to use a different ordering, you can supply another ordering as an extra argument to the factory method. For instance, we can use the reverse ordering on integers instead of the natural ordering.

scala> val ord = Ordering.by[Int,Int](x => -x)
ord: scala.math.Ordering[Int] =
scala.math.Ordering$$anon$9@59ed63ee

val m2 = PriorityMap('a' -> 1, 'b' -> 2, 'c' -> 0)(ord)
m2: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(b -> 2, a -> 1, c -> 0)

If you remove a key/value pair or add one with the right type, you get back a new priority map.

scala> m - 'a'
res2: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(c -> 0, b -> 2)

scala> m + ('b' -> -1)
res3: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(b -> -1, c -> 0, a -> 1)

Care has to be taken if a key/value pair with a value of a different type is added. Since—unlike regular maps—priority maps are not covariant in their value type, it is for example not possible to add a value of type String to a priority map with values of type Int and get back another priority map. In fact, covariance is ruled out by the possibility that there may be no implicit ordering defined for the common supertype (or one that is not compatible with the ordering defined for the original value type). Since priority maps are compatible with regular maps, adding an incompatible binding therefore results in a regular map instead of a priority map.

scala> m + scala> m + ('a' -> "Hello")
res4: scala.collection.immutable.Map[Char,Any] =
Map(a -> Hello, b -> 2, c -> 0)

Obtaining or removing an entry with the minimal or maximal value can be done via the standard methods head, tail, last and init.

scala> m.head
res5: (Char, Int) = (c,0)

scala> m.tail
res6: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(a -> 1, b -> 2)

scala> m.last
res7: (Char, Int) = (b,2)

scala> m.init
res8: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(c -> 0, a -> 1)

Higher-order methods like map and filter can be used as well and return priority maps if possible.

scala> m map { case (k,v) => (k,-v) }
res9: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(b -> -2, a -> -1, c -> 0)

scala> m filter { case (k,v) => v % 2 == 0 }
res10: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(c -> 0, b -> 2)

Priority maps also offer methods from, until and range which return a submap where all entries have values inside the given range.

scala>m.from(1)
res11: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(a -> 1, b -> 2)

scala> m.until(2)
res12: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(c -> 0, a -> 1)

scala> m.range(1,2)
res13: de.ummels.prioritymap.PriorityMap[Char,Int] =
PriorityMap(a -> 1)

If you want to give scala-prioritymap a spin, you can include it in your SBT project by adding the following line to your build file:

libraryDependencies += "de.ummels" %% "scala-prioritymap" % "0.1.0"

Or if you want to check out the source, take a look on GitHub.

In the next post, we’ll see how we can use priority maps to implement Dijkstra’s algorithm in Scala.