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

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 类型定义一个案例类，与 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

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

Answer 3

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

本次讲座解释了这个想法（但在Python中......抱歉）。

Answer 4

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

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

如果你的预制堆带有一个接受指向节点的指针的 DK 操作，那么你可以简单地构建一个自制节点对象的堆，它只需将指针包装在一个类中，这样你就可以提供比较运算符（需要建立一个堆）。

Answer 5

我已经实现了一个 类 来完全满足您的需要：

• 插入是 enqueue
• extractMin 是 dequeue
• decreaseKey 是 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
  }
}