How to use priority queues in Scala?

Question

I am trying to implement A* search in Scala (version 2.10), but I've ran into a brick wall - I can't figure out how to use Scala's Priority Queue.

I have a set of squares, represented by (Int, Int)s, and I need to insert them with priorities represented by Ints. In Python you just have a list of key, value pairs and use the heapq functions to sort it.

So how do you do this?

Answer 1

There is actually pre-defined lexicographical order for tuples -- but you need to import it:

import scala.math.Ordering.Implicits._

Moreover, you can define your own ordering. Suppose I want to arrange tuples, based on the difference between first and second members of the tuple:

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

scala> def diff(t2: (Int,Int)) = math.abs(t2._1 - t2._2)
// diff: (t2: (Int, Int))Int

scala> val x = new PriorityQueue[(Int, Int)]()(Ordering.by(diff))
// x: scala.collection.mutable.PriorityQueue[(Int, Int)] = PriorityQueue()

scala> x.enqueue(1 -> 1)

scala> x.enqueue(1 -> 2)

scala> x.enqueue(1 -> 3)

scala> x.enqueue(1 -> 4)

scala> x.enqueue(1 -> 0)

scala> x
// res5: scala.collection.mutable.PriorityQueue[(Int, Int)] = PriorityQueue((1,4), (1,3), (1,2), (1,1), (1,0))