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

您只需提及队列项目的顺序。以下代码将用于此目的。

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

避免使用反向，因为这会产生不必要的开销。

Answer 2

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

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

Answer 3

<代码>优先队列。应用和优先队列。empty都采用隐式排序实例，该实例将用于排序内容。根据该排序，head将是“最大”值。您将获得元组的默认值，这是元组元素的字典排序，这不是您想要的，因为它将使第一个元素最大的元组成为头部。

有几种方法可以解决这个问题。最简单的方法就是调用。在队列上反转，这将为您提供一个具有相同内容但顺序相反的新队列，这意味着具有最小值的元组将是头部。

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

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
)

这可能比反转队列更有效率，但可能还不足以让人担心，因此您应该选择您认为最优雅的方法。