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 实例，该实例将用于对内容进行排序 - 头部将是根据该顺序的“最大”值。您将获得元组的默认值，这是元组元素的字典顺序，这不是您想要的，因为它会使第一个元素最大的元组成为头部。

有几种方法可以解决此问题。最简单的方法就是在队列上调用 .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
)

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