Scala命令优先级队列始终具有最低编号作为头部,升序

Question

我想获得一个代码示例,它可以完成优先级队列中项目的升序排序.

我想存储Tuple2(Int, String)在优先级队列中,以便按元组的第一个元素按升序排序.如果我的优先级队列被调用pq,我打电话,pq.head我想得到数量最少的元组,同样的调用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))

如何在插入上面的第一个元素应用升序？

谢谢

Answer 1

PriorityQueue.apply 和 PriorityQueue.empty都采用Ordering将用于对内容进行排序的隐式实例 - 根据该排序,head将是"最大"值.你得到了元组的默认值,这是元组元素的词典排序,这不是你想要的,因为它会使元组中头部的第一个元素最大.

有几种方法可以解决这个问题.最简单的就是打电话.reverse你的队列,这将为你提供一个新的队列,它具有相同的内容,但顺序相反,这意味着具有最低值的元组将是头部.

您还可以在创建队列时提供自己的顺序:

import scala.collection.mutable.PriorityQueue

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

或者,如果您明确不希望查询第二个元素:

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

这可能比撤消队列更有效,但可能不足以担心,因此您应该选择您认为最优雅的方法.

Answer 2

如果您需要的只是反转隐式排序，则可以立即反转队列：

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

Answer 3

您所需要做的就是提及队列项目的排序。以下代码将达到目的。

  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()))

避免使用，reverse因为它会产生不必要的开销。