Изменение приоритета элементов в очереди приоритетов

Использование Scala 2.9 для реализации своего рода алгоритма Дейкстры (псевдокод)

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 ?

  • Кто-нибудь знает, является ли отсутствие такого метода намеренным и будет ли он рекомендован для восстановления очереди после изменения приоритета некоторых элементов (возможно, посмотрите обсуждение Priority queue с динамическими приоритетами элементов )?

15
задан Community 23 May 2017 в 11:45
поделиться