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

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) Removing an item from a priority queue .

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

• 有谁知道缺少这种方法是否是设计使然，并且会被推荐在更改某些项目的优先级后重建队列(也许看看关于 Priority queue with dynamic item priorities 的讨论)？

Answer 1

为 PriorityQueue 类型定义一个案例类以与 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)