如何在 Scala 中使用优先队列? [英] How to use priority queues in Scala?

问题描述

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

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)

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

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.

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

So how do you do this? I'm surprised by the complete lack of online information, given how simple it should be.

推荐答案

其实有元组的预定义字典顺序 -- 但是你需要导入它:

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

这篇关于如何在 Scala 中使用优先队列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！