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

Question

我正在尝试在Scala(版本2.10)中实现A*搜索,但我遇到了一堵砖墙 - 我无法弄清楚如何使用Scala的优先级队列.这似乎是一个简单的任务,但在Google上搜索没有发现任何东西(除了在2.8版本中停止工作的单个代码示例)

我有一组由(Int, Int)s 表示的正方形,我需要用Ints 表示的优先级插入它们.在Python中它很简单,因为你只有一个键值对的列表,并使用heapq函数对它进行排序.但看起来Scala的元组甚至不具有可比性.

那你怎么做的？鉴于它应该是多么简单,我对完全缺乏在线信息感到惊讶.

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