scala - 如何在 Scala 中使用优先队列？

Question

我正在尝试在 Scala(2.10 版)中实现 A* 搜索，但我遇到了砖墙 - 我不知道如何使用 Scala 的优先队列。这似乎是一项简单的任务，但在 Google 上搜索没有任何结果(除了在 2.8 版中停止工作的单个代码示例)

我有一组正方形，由 (Int, Int) 表示s，我需要用 Int 表示的优先级插入它们s。在 Python 中，这非常简单，因为您只有一个键值对列表并使用 heapq 函数对其进行排序。但似乎 Scala 的元组甚至没有可比性。

那么你怎么做呢？考虑到它应该是多么简单，我对完全缺乏在线信息感到惊讶。

Answer 1

居然还有pre-defined lexicographical order for tuples -- but you need to import it :

import scala.math.Ordering.Implicits._

此外，您可以定义自己的排序。
假设我想根据元组的第一个和第二个成员之间的差异来排列元组:

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