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

发布时间：2020-12-16 09:13:06 所属栏目：安全来源：网络整理

导读：我试图在 Scala(2.10版)中实现A *搜索,但是我遇到了一堵砖墙 – 我不知道如何使用Scala的优先级队列.这似乎是一个简单的任务,但在Google上搜索并没有发现任何东西(除了在2.8版本中停止恢复的单个代码示例) 我有一组由(Int,Int)s表示的正方形,我需要以Ints表

我试图在 Scala(2.10版)中实现A *搜索,但是我遇到了一堵砖墙 – 我不知道如何使用Scala的优先级队列.这似乎是一个简单的任务,但在Google上搜索并没有发现任何东西(除了在2.8版本中停止恢复的单个代码示例)

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

那你该怎么做呢？我很惊讶,完全缺乏在线信息,因为它应该是多么简单.

解决方法

其实是 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),2),1),0))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!