如何在 Scala 中使用优先队列？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14927395/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to use priority queues in Scala?
提问by Antimony
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. It seems like a simple task, but searching on Google didn't turn up anything (except for a single code sample that stopped working back in version 2.8)
我正在尝试在 Scala（2.10 版）中实现 A* 搜索，但我遇到了砖墙 - 我不知道如何使用 Scala 的优先队列。这似乎是一项简单的任务，但在 Google 上搜索没有任何结果（除了在 2.8 版中停止工作的单个代码示例）
I have a set of squares, represented by (Int, Int)s, and I need to insert them with priorities represented by Ints. In Python it's pretty simple, since you just have a list of key, value pairs and use the heapq functions to sort it. But it appears that Scala's tuples aren't even comparable.
我有一组正方形，用(Int, Int)s表示，我需要用Ints表示的优先级插入它们。在 Python 中，这非常简单，因为您只有一个键值对列表并使用 heapq 函数对其进行排序。但似乎 Scala 的元组甚至没有可比性。
So how do you do this? I'm surprised by the complete lack of online information, given how simple it should be.
那么你怎么做呢？考虑到它应该是多么简单，我对完全缺乏在线信息感到惊讶。
回答by om-nom-nom
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))
回答by minopret
Indeed, there is no implicit ordering on pairs of integers (a, b). What would it be? Perhaps they are both positive and you can use (a - 1.0/b)? Or they are not, and you can use, what, (a + atan(b/pi))? If you have an ordering in mind, you can consider wrapping your pairs in a type that has your ordering.
实际上，整数对 (a, b) 没有隐式排序。那会是什么？也许它们都是正数，您可以使用 (a - 1.0/b) 吗？或者它们不是，您可以使用什么，(a + atan(b/pi))？如果您有订购的想法，您可以考虑将您的配对包装在您订购的类型中。
