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

Question

提问by binuWADa

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

使用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)
  }
}

I'd like to change priority of an item in Scala's collection.mutable.PriorityQueue.

我想在 Scala 的collection.mutable.PriorityQueue.

Therefore tried to

因此试图

remove item
change priority
reinsert into queue.

除去项目
更改优先级
重新插入队列。

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.

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

How this task can be done with scala.collection.mutable.PriorityQueueor do I have to use java.util.PriorityQueueinstead?
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)?

如何完成此任务scala.collection.mutable.PriorityQueue或我必须使用它java.util.PriorityQueue吗？
有谁知道缺乏这种方法是否是设计使然，并且建议在更改某些项目的优先级后重建队列（也许可以查看有关具有动态项目优先级的优先级队列的讨论）？

Answer 1

回答by Brian

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.

为 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)

Answer 2

回答by Erik P.

Priority queues are commonly implemented with heaps. Binary heaps are commonly implemented using arrays, and if the element you want to remove is not on the path between the root of the heap and its last element in the array ordering, then there is no obvious way to remove it. I assume that this is why Scala doesn't offer removal of arbitrary elements. However, if you implement your own heap, it's easy enough to implement decrease-key for a binary (min-)heap: you just compare the new priority for a node Nto its parent's priority, and if necessary exchange the two. Do this repeatedly until Nis at the top or N's parent has lower priority than Nitself.

优先级队列通常用堆实现。二元堆通常使用数组实现，如果要删除的元素不在堆的根和数组排序中的最后一个元素之间的路径上，则没有明显的方法可以删除它。我认为这就是 Scala 不提供删除任意元素的原因。但是，如果您实现自己的堆，那么实现二元（最小）堆的减少键就很容易：您只需将节点的新优先级N与其父级的优先级进行比较，并在必要时交换两者。重复执行此操作，直到N位于顶部或N其父级的优先级低于N自身。

Answer 3

回答by sumx

I don't have experience with Scala but the problem I see is that a plain priority queue is not enough for Dijkstra since you need to know where a particular vertex is stored in the queue before you can do a decrease-key. In other words, a dictionary (hash table) is required to map vertex ids to indices within the heap in expected constant time. Then you get an overall O(log n) for the decrease-key. It seems unlikely to me that such a functionality can be found in a standard library. Writing a suitable class from scratch should be easy though.

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

The code at the end of this lectureexplains the idea (but in python.. sorry).

本讲座末尾的代码解释了这个想法（但在 python 中......抱歉）。

Answer 4

回答by Gaminic

Not a Scala user, but so far I've never seen a built-in/pre-made Heap implementation that allows for Decrease Key, because Decrease Key is only effective if you can provide (the location of) the element being DK'd.

不是 Scala 用户，但到目前为止我从未见过允许减少键的内置/预制堆实现，因为减少键只有在您可以提供被 DK 的元素（的位置）时才有效.

The easiest way of getting the DK operation is to implement the Heap yourself. My method is usually to keep my Elements separate (in an unorganized array/vector/linked list) and to build a Heap of pointers-to-Elements (or array-indeces). Then, given a Heap node, you can look up the element by accessing it in the array (dereference or index-lookup). To support DK and/or Random Delete, you can add an additional variable to the Element that points to the Heap node (or keeps the index, if array-based Heap). This allows you to have O(1) access in either direction.

获取DK操作最简单的方法就是自己实现Heap。我的方法通常是将我的元素分开（在一个无组织的数组/向量/链表中）并构建一个指向元素的指针（或数组索引）堆。然后，给定一个堆节点，您可以通过在数组中访问它来查找元素（取消引用或索引查找）。为了支持 DK 和/或随机删除，您可以向指向堆节点的元素添加一个额外的变量（或保留索引，如果基于数组的堆）。这使您可以在任一方向上进行 O(1) 访问。

If your pre-made Heap comes with a DK operation that accepts a pointer to the Node, then you can simply build a Heap of self-made Node Objects, which simply wrap the Pointer in a class so you can provide comparison operators (required to build a Heap of them).

如果您的预制 Heap 带有接受指向 Node 的指针的 DK 操作，那么您可以简单地构建一个自制 Node Objects 的 Heap，它只需将 Pointer 包装在一个类中，以便您可以提供比较运算符（需要建立一堆）。

Answer 5

回答by Leonardo

I have implemented a classto do exactly what you need:

我已经实现了一个类来做你所需要的：

insert is enqueue
extractMin is dequeue
decreaseKey is putValue

插入是 enqueue
提取最小值是 dequeue
减少键是 putValue

import scala.annotation.tailrec
import scala.collection.mutable.{ArrayBuffer, Map}
import scala.util.Try

class HeapedMap[K, V] (implicit ord: Ordering[V]){
  val dict = Map[K,Int]() // Keeps index of key withing vector
  val vector = ArrayBuffer[(K,V)]()

  override def toString(): String = vector.toString
  def toMap(): scala.collection.immutable.Map[K,V] = dict.mapValues(vector(_)._2).toMap
  def toSeq(): Seq[(K,V)] = vector
  def toList(): List[(K,V)] = vector.toList

  private def parent(i: Int): Int = (i - 1) / 2
  private def right(i: Int): Int = (i * 2 + 1) + 1
  private def left(i: Int): Int = (i * 2 + 1)
  private def exists(i: Int): Boolean = Try(vector(i)).isSuccess
  private def compare(x: V, y: V): Boolean = ord.lteq(x,y)
  private def swap(i: Int, j: Int): Unit = {
    val aux = vector(i)
    vector(i) = vector(j)
    dict(vector(i)._1) = i
    vector(j) = aux
    dict(vector(j)._1) = j
  }
  private def replace(i: Int, j: Int): Unit = {
    dict -= vector(i)._1
    vector(i) = vector(j)
    dict(vector(i)._1) = i
    vector.remove(j)
  }

  private def insert(key: K, value: V): Unit = {
    vector += ((key, value))
    dict(key) = vector.size - 1
    bubbleUp(vector.size - 1)
  }

  private def delete(i: Int): Unit = {
    if (vector.size == 1) {
      dict -= vector(0)._1
      vector.remove(0)
    } else {
      replace(i, vector.size - 1)
      bubbleDown(i)
    }
  }

  def isEmpty(): Boolean = vector.isEmpty

  def enqueue(key: K, value: V): Unit = {
    if (!dict.contains(key)) {
      insert(key,value)
    }
    // TODO: handle when it already contains the key
  }

  @tailrec
  private def bubbleUp(i: Int): Unit = {
    val p = parent(i)
    if ((p != i) && (!compare(vector(p)._2, vector(i)._2))) {
      swap(p, i)
      bubbleUp(p)
    }
  }

  @tailrec
  private def bubbleDown(i: Int): Unit = {
    var largest = i
    val l = left(i)
    val r = right(i)
    if ((exists(l)) && (compare(vector(l)._2, vector(largest)._2))) {
      largest = l
    }
    if ((exists(r)) && (compare(vector(r)._2, vector(largest)._2))) {
      largest = r
    }

    if (largest != i) {
      swap(i, largest)
      bubbleDown(largest)
    }
  }

  def dequeue(): Option[(K, V)] = {
    val optionRoot = vector.headOption
    if (optionRoot.isDefined) {
        delete(0)
    }
    optionRoot
  }

  def dequeueAll(): Seq[(K,V)] = {
    val resp = ArrayBuffer[(K,V)]()
    var x = dequeue
    while (x.isDefined) {
      resp += x.get
      x = dequeue
    }
    resp
  }

  def headOption(): Option[(K,V)] = vector.headOption
  def get(k: K): Option[V] = {
    dict.get(k) match {
      case Some(i) => Some(vector(i)._2)
      case None => None
    }
  }

  // change values and heapify
  // * PriorityQueue does not have this feature
  def putValue(key: K, value: V): Unit = {
    val optionOldValue = get(key)
    if (optionOldValue.isDefined) {
      val oldValue = optionOldValue.get
      val i = dict(key)
      vector(i) = (key, value)
      if (compare(value, oldValue)) {
        bubbleUp(i)
      } else {
        bubbleDown(i)
      }
    } else {
      // if key does not exist, insert it
      insert(key,value)
    }
  }

  // different from dequeue, removes an arbitrary element
  def remove(key: K): Unit = {
    if (dict.contains(key)) {
      delete(dict(key))
    }
    // TODO: handle when it does not contain the key
  }
}

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

提问by binuWADa

回答by Brian

回答by Erik P.

回答by sumx

回答by Gaminic

回答by Leonardo

相关推荐

最近更新

标签

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

提问by binuWADa

回答by Brian

回答by Erik P.

回答by sumx

回答by Gaminic

回答by Leonardo

相关推荐

在 Scala 中对两个列表求和的最简单方法？

scala 中的字符串连接是否和 Java 中的一样昂贵？

Scala 地图 foreach

scala sbt：选择运行的主类

相关推荐

最近更新

标签