Scala ordered priority queue that always has the lowest number as the head, ascending order

Question

I'd like to get a code sample that accomplishes ascending ordering of items in a priority queue.

I'd like to store Tuple2(Int, String) inside a priority queue so that it is ordered by the first element of the tuple in ascending order. If my priority queue is called pq and I call pq.head I'd like to get the tuple with the lowest number, same thing with calling pq.dequeue.

scala> val pq = scala.collection.mutable.PriorityQueue[(Int, String)]()
pq: scala.collection.mutable.PriorityQueue[(Int, String)] = PriorityQueue()

scala> pq += Tuple2(8, "eight")
res60: pq.type = PriorityQueue((8,eight))

scala> pq += Tuple2(4, "four")
res61: pq.type = PriorityQueue((8,eight), (4,four))

scala> pq += Tuple2(7, "seven")
res62: pq.type = PriorityQueue((8,eight), (4,four), (7,seven))

How to apply ascending ordering by first element at time of insertion to the above?

Thanks

Answer 1

PriorityQueue.apply and PriorityQueue.empty both take an implicit Ordering instance that will be used to order the contents—the head will be the "largest" value according to that ordering. You're getting the default one for tuples, which is a lexicographic ordering on the elements of the tuple, which isn't what you want, since it'll make the tuple with the largest first element the head.

There are a couple of ways you can solve this issue. The easiest is just to call .reverse on your queue, which will give you a new queue with the same contents but the opposite ordering, which means the tuple with the lowest value will be the head.

You can also provide your own ordering when creating the queue:

import scala.collection.mutable.PriorityQueue

val pq = PriorityQueue.empty[(Int, String)](
  implicitly[Ordering[(Int, String)]].reverse
)

Or if you explicitly don't want the second element to be consulted:

val pq = PriorityQueue.empty[(Int, String)](
  Ordering.by((_: (Int, String))._1).reverse
)

This is possibly a little more efficient than reversing the queue, but probably not enough to worry about, so you should just choose the approach that you find most elegant.

Answer 2

If all you need is reversing the implicit ordering, you could just reverse the queue right away:

val pq = PriorityQueue.empty[(Int, String)].reverse

Answer 3

All you need to do is to mention ordering of the queue items. The following code will serve the purpose.

  def ascendingOrder(tuple2: (Int, String)) = -tuple2._1
  val pq = PriorityQueue[(Int, String)]()(Ordering.by(ascendingOrder))
  pq += Tuple2(8, "eight")
  pq += Tuple2(4, "four")
  pq += Tuple2(7, "seven")
  for (i <- 1 to 3) (println(pq.dequeue()))

Avoid using reverse as it will create unnecessary overheads.