在优先级队列更改项目的优先级 [英] Change priority of items in a priority queue

问题描述

使用Scala 2.9实现了一种Dijkstra算法的（伪code）

Using Scala 2.9 to implement a kind of Dijkstra algorithm (pseudo code)

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

我想改变一个项目的优先级Sc​​ala的 collection.mutable.PriorityQueue 。

因此​​试图

• 删除项目
• 更改优先级
• 重新插入到队列中。

但我不能找到一种方法，要么更新优先级或删除特定项目（不 一定是头元素），如 java.util.PriorityQueue中的＃删除（对象）作为并列的 删除的项目从优先级队列。

But I can't find a method to either update priority or remove a specific item (not necessarily head element) like java.util.PriorityQueue#remove(Object) as apposed in Removing an item from a priority queue.

• 如何这个任务可以用 scala.collection.mutable.PriorityQueue 完成 或者我必须使用 java.util.PriorityQueue中呢？

• How this task can be done with scala.collection.mutable.PriorityQueue or do I have to use java.util.PriorityQueue instead?

有谁知道缺少这样的方法是否是设计使然，它会推荐 改变一些项目优先后重建队列（也许一起来看看关于<讨论href="http://stackoverflow.com/questions/2288241/priority-queue-with-dynamic-item-priorities">Priority排队的动态项的优先级的）？

Does anyone know whether lack of such a method is by design and it would be recommended to rebuild the queue after changing priority of some items (maybe take a look at discussion about Priority queue with dynamic item priorities)?

推荐答案

定义的情况下类时Queue类型使用var优先使用可以让你找到它，并发生变异的优先级。时Queue再有新的价值。为了得到正确的顺序，我不得不克隆它其中重排/强制排序。有可能是一个更好的办法做到这一点没有克隆。

Defining a case class for the PriorityQueue type to use with var for priority allows you to find it and mutate the priority. The PriorityQueue then has this new value. To get the ordering correct I had to clone it which reorders/forces the ordering. There might be a better way to do this without cloning.

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)

这篇关于在优先级队列更改项目的优先级的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！