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

Question

用Scala2.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中项的优先级。

因此试图

• 移除项目
• 变更优先级
• 重新插入队列。

但是，我找不到一种方法来更新优先级或删除特定项(不一定是head元素)，比如java.util.PriorityQueue#remove(Object)在从优先级队列中删除项中的位置。

• 如何使用scala.collection.mutable.PriorityQueue完成此任务，还是必须使用java.util.PriorityQueue？
• 是否有人知道缺乏这样的方法是否是设计好的，并建议在更改某些项的优先级后重新构建队列(也许可以看看关于具有动态项优先级的优先级队列的讨论)？

Answer 1

为PriorityQueue类型定义一个case类以便与var for优先级一起使用，可以让您找到它并更改优先级。然后，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)

Answer 2

优先级队列通常用堆来实现。二进制堆是常用数组实现，如果要删除的元素不在堆的根和数组排序中的最后一个元素之间的路径上，那么就没有明显的方法来删除它。我假设这就是Scala不提供删除任意元素的原因。但是，如果您实现了自己的堆，那么很容易实现二进制(min-)堆的减键:您只需将节点N的新优先级与其父级的优先级进行比较，并在必要时交换这两个优先级。重复这样做，直到N处于顶端，或者N的父级优先级低于N本身。

Answer 3

我对Scala没有经验，但我看到的问题是，对于Dijkstra来说，简单的优先级队列是不够的，因为您需要知道队列中存储特定顶点的位置，然后才能执行减键操作。换句话说，需要字典(哈希表)在预期的恒定时间内将顶点is映射到堆中的索引。然后得到减少键的整体O(log )。在我看来，这样的功能不太可能在标准库中找到。不过，从头开始编写一个合适的类应该很容易。

这次讲座末尾的代码解释了这个想法(但是在python中)。对不起)。