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

Используя 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?

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

Ответы

Ответ 1

Определение класса case для типа 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)

Ответ 2

Очереди приоритетов обычно реализуются с помощью кучи. Двоичные кучи обычно реализуются с использованием массивов, и если элемент, который вы хотите удалить, не находится на пути между корнем кучи и его последним элементом в упорядочении массива, то нет очевидного способа его удалить. Я предполагаю, что именно поэтому Scala не предлагает удаление произвольных элементов. Однако, если вы реализуете свою собственную кучу, достаточно просто реализовать уменьшающий ключ для двоичной (min-) кучи: вы просто сравниваете новый приоритет для node N с его родительским приоритетом и при необходимости обмениваете два. Повторяйте это до тех пор, пока N не будет наверху или N родительский имеет более низкий приоритет, чем N.

Ответ 3

У меня нет опыта работы с Scala, но проблема, которую я вижу, заключается в том, что для Dijkstra недостаточно простой очереди очередности, так как вам нужно знать, где определенная вершина хранится в очереди, прежде чем вы сможете сделать сокращение, ключ. Другими словами, для отображения вершинных идентификаторов в индексы в куче в ожидаемое постоянное время требуется словарь (хеш-таблица). Затем вы получаете общий O (log n) для клавиши уменьшения. Мне кажется маловероятным, что такую ​​функциональность можно найти в стандартной библиотеке. Написание подходящего класса с нуля должно быть легко.

Код в конце эта лекция объясняет идею (но в python.. извините).

Ответ 4

Не пользователь Scala, но до сих пор я никогда не видел встроенную/предварительно созданную реализацию кучи, которая позволяет использовать Key Decrease, потому что Key Decrease эффективен только в том случае, если вы можете предоставить (местоположение) элемент DK'd.

Самый простой способ получить операцию DK - реализовать кучу самостоятельно. Мой метод обычно заключается в том, чтобы отдельные элементы были разделены (в неорганизованном массиве/векторе/связанном списке) и для создания кучи указателей-элементов (или массивов-индексов). Затем, учитывая кучу node, вы можете найти элемент, обратившись к нему в массиве (разыменование или индексный поиск). Для поддержки DK и/или случайного удаления вы можете добавить дополнительную переменную к элементу, который указывает на кучу node (или хранит индекс, если массив на основе массива). Это позволяет вам иметь доступ O (1) в любом направлении.

Если ваша готовая куча поставляется с операцией DK, которая принимает указатель на node, тогда вы можете просто создать кучу самодельных объектов node, которые просто переносят указатель в класс, чтобы вы может предоставить операторов сравнения (необходимых для создания кучи).