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

Question

我正在尝试在Scala（版本2.10）中实现A *搜索，但我遇到了一个瓶颈 - 我无法弄清如何使用Scala的优先队列。

我有一组由(Int, Int)表示的方块，并且需要使用由Int表示的优先级插入它们。在Python中，您只需拥有一个键值对列表并使用heapq函数进行排序。

那么你该怎么做呢？

- Antimony

Answer 1

实际上，对于元组有预定义的词典顺序 -- 但你需要导入它：

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

- om-nom-nom

---

谢谢。我之前尝试导入scala.math.Ordering.Implicits._，但是我漏掉了一个句号。 - Antimony

@Antimony，请看编辑。我之前误导了你使用+=运算符，你需要使用.enqueue方法。 - om-nom-nom

Answer 2

事实上，对于整数对(a, b)而言，不存在隐式的排序。那么应该如何排序呢？也许它们都是正数，你可以使用(a - 1.0/b)吗？或者它们不是正数，你可以使用什么呢，(a + atan(b/pi))？如果您有某种排序方式，请考虑将您的整数对包装在一个具有您排序方式的类型中。

- minopret

---

自然排序是按字典顺序排列的，这就是C++和Python所做的。我太傻了，以为Scala至少和C++一样功能强大。 - Antimony

@Antimony：只是想澄清一下：C++语言及其标准库本身包含此排序吗？ - Randall Schulz