更改优先级队列中项目的优先级

Question

使用Scala 2.9实现一种Dijkstra算法(伪代码)

val queue = new PriorityQueue
queue.insert(...)
while (!queue.isEmpty) {
  val u = queue.extractMin
  queue.foreach { v =>
    if (condition(u, v))
      queue.decreaseKey(v, newPriority)
  }
}

我想改变Scala中项目的优先级collection.mutable.PriorityQueue.

因此试图

• 除去项目
• 改变优先权
• 重新插入队列.

但是我找不到一种方法来更新优先级或删除特定项目(不一定是头元素),就像从优先级队列java.util.PriorityQueue#remove(Object)中 删除项目一样.

• 如何完成此任务scala.collection.mutable.PriorityQueue 或者我必须使用java.util.PriorityQueue？

• 有没有人知道这种方法是否缺乏设计,并且建议在更改某些项目的优先级后重建队列(可能需要查看有关优先级队列与动态项目优先级的讨论)？

Answer 1

为 PriorityQueue 类型定义一个 case 类，与 var 一起使用作为优先级，这样您就可以找到它并改变优先级。然后 PriorityQueue 就有这个新值。为了获得正确的排序，我必须克隆它，这会重新排序/强制排序。可能有更好的方法来做到这一点，而无需克隆。

case class Elem(var priority: Int, i: Int)

def MyOrdering = new Ordering[Elem] {
  def compare(a : Elem, b : Elem) = a.priority.compare(b.priority)
}

val pq = new scala.collection.mutable.PriorityQueue[Elem]()(MyOrdering)  ++ List(Elem(1,1), Elem(0,0), Elem(2,2))

pq.find(x => x.priority == 0) match {
  case Some(elem: Elem) => elem.priority = 3
  case None => println("Not found")
}

val pq2 = pq.clone
println(pq2)
println(pq2.dequeue)
println(pq2.dequeue)
println(pq2.dequeue)



:load SO.scala
Loading SO.scala...
defined class Elem
PileOrdering: java.lang.Object with Ordering[Elem]
pq: scala.collection.mutable.PriorityQueue[Elem] = PriorityQueue(Elem(2,2), Elem(0,0), Elem(1,1))
pq2: scala.collection.mutable.PriorityQueue[Elem] = PriorityQueue(Elem(3,0), Elem(2,2), Elem(1,1))
PriorityQueue(Elem(3,0), Elem(2,2), Elem(1,1))
Elem(3,0)
Elem(2,2)
Elem(1,1)