Обновление Java PriorityQueue, когда его элементы меняют приоритет

Я пытаюсь использовать PriorityQueue упорядочить объекты с помощью Comparator,

Это может быть легко достигнуто, но переменные класса объектов (с помощью которых компаратор вычисляет приоритет) могут измениться после начальной вставки. Большинство людей предложили простое решение удаления объекта, обновления значений и его повторной вставки, поскольку именно в этом случае запускается компаратор приоритетной очереди.

Есть ли лучший способ, чем просто создать класс-оболочку вокруг PriorityQueue, чтобы сделать это?

Источник

8 ответов

Решение

Вы должны удалить и повторно вставить, поскольку очередь работает, помещая новые элементы в соответствующее положение, когда они вставляются. Это намного быстрее, чем альтернатива поиска элемента с наивысшим приоритетом каждый раз, когда вы выходите из очереди. Недостатком является то, что вы не можете изменить приоритет после вставки элемента. TreeMap имеет такое же ограничение (как и HashMap, который также прерывается, когда хеш-код его элементов изменяется после вставки).

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

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

Источник

Я не знаю, есть ли реализация Java, но если вы много меняете значения ключа, вы можете использовать кучу Фибоначчи, которая имеет амортизированную стоимость O(1), чтобы уменьшить значение ключа записи в куче, скорее чем O(log(n)), как в обычной куче.

Источник

Одно простое решение, которое вы можете реализовать, - просто снова добавить этот элемент в очередь с приоритетами. Это не изменит способ извлечения элементов, хотя он будет занимать больше места, но это также не будет слишком много, чтобы повлиять на ваше время выполнения.

Чтобы доказать это, рассмотрим алгоритм Дейкстры ниже.

public int[] dijkstra() {
int distance[] = new int[this.vertices];
int previous[] = new int[this.vertices];
for (int i = 0; i < this.vertices; i++) {
    distance[i] = Integer.MAX_VALUE;
    previous[i] = -1;
}
distance[0] = 0;
previous[0] = 0;
PriorityQueue<Node> pQueue = new PriorityQueue<>(this.vertices, new NodeComparison());
addValues(pQueue, distance);
while (!pQueue.isEmpty()) {
    Node n = pQueue.remove();
    List<Edge> neighbours = adjacencyList.get(n.position);
    for (Edge neighbour : neighbours) {
        if (distance[neighbour.destination] > distance[n.position] + neighbour.weight) {
            distance[neighbour.destination] = distance[n.position] + neighbour.weight;
            previous[neighbour.destination] = n.position;
            pQueue.add(new Node(neighbour.destination, distance[neighbour.destination]));
        }
    }
}
return previous;

}

Здесь наш интерес в соответствии pQueue.add(new Node(neighbour.destination, distance[neighbour.destination]));Я не изменяю приоритет конкретного узла, удаляя его и добавляя снова, я просто добавляю новый узел с тем же значением, но с другим приоритетом. Теперь во время извлечения я всегда получу этот узел первым, потому что здесь реализована минимальная куча, а узел со значением, большим, чем это (меньший приоритет), всегда извлекается впоследствии, и таким образом все соседние узлы уже будут ослаблены, когда менее предварительно. элемент будет извлечен.

Источник

Без повторной реализации очереди приоритетов самостоятельно (поэтому, используя только utils.PriorityQueue) у вас есть два основных подхода:

1) Снимаем и ставим обратно

Удалите элемент, затем верните его с новым приоритетом. Это объясняется в ответах выше. Удаление элемента - O (n), поэтому этот подход довольно медленный.

2) Используйте карту и храните устаревшие элементы в очереди

Держать HashMapпункта -> приоритет. Ключи карты - это элементы (без их приоритета), а значения карты - это приоритеты.

Синхронизируйте его с PriorityQueue (т.е. каждый раз, когда вы добавляете или удаляете элемент из очереди, обновляйте карту соответствующим образом).

Теперь, когда вам нужно изменить приоритет элемента, просто добавьте тот же элемент в очередь с другим приоритетом. Когда вы опрашиваете элемент из очереди, проверьте, совпадает ли его приоритет с приоритетом вашей карты. Если нет, то откажитесь от этого и снова проведите опрос.

Если вам не нужно слишком часто менять приоритеты, второй подход будет более быстрым. Ваша куча будет больше, и вам, возможно, придется опрашивать больше раз, но вам не нужно искать свой предмет. Операция изменения приоритета будет O(f(n)log n*) , где f(n) - количество операций изменения приоритета для каждого элемента, а n * - фактический размер вашей кучи (который равен n * f ( п)).

Я считаю, что если f(n) равно O (n / logn)(например, f(n) = O(sqrt(n)), это быстрее, чем первый подход.

Примечание: в приведенном выше объяснении под приоритетом я подразумеваю все переменные, которые используются в вашем компараторе. Также ваш товар необходимо реализовать equals а также hashcode, и оба метода не должны использовать переменные приоритета.

Источник

Это зависит от того, имеете ли вы непосредственный контроль над изменением значений.

Если вы знаете, когда значения изменяются, вы можете удалить и заново вставить (что на самом деле довольно дорого, поскольку удаление требует линейного сканирования кучи!). Кроме того, для этой ситуации вы можете использовать структуру UpdatableHeap (но не в стандартной java). По сути, это куча, которая отслеживает положение элементов в хэш-карте. Таким образом, когда приоритет элемента изменяется, он может восстановить кучу. В-третьих, вы можете искать кучу Фибоначчи, которая делает то же самое.

В зависимости от частоты обновления может также работать линейное сканирование / быстрая сортировка / быстрый выбор каждый раз. В частности, если у вас гораздо больше обновлений, чем pull с, это путь. QuickSelect, вероятно, лучше всего, если у вас есть пакеты обновлений, а затем пакеты операций извлечения.

Источник

Для запуска reheapify попробуйте это:

if(!priorityQueue.isEmpty()) { priorityQueue.add(priorityQueue.remove()); }

Источник

Что-то, что я пробовал, и это работает до сих пор, смотрит, чтобы увидеть, совпадает ли ссылка на объект, который вы изменяете, с заголовком PriorityQueue, если это так, то вы опросите (), измените, затем вставьте заново; иначе вы можете изменить без опроса, потому что, когда опрашивается голова, куча в любом случае кучи.

ВНИЗ: Это изменяет приоритет для объектов с таким же приоритетом.

Источник

Есть ли лучший способ сделать это, кроме как просто создать класс-оболочку вокруг PriorityQueue?

Это зависит от определения «лучше» и реализации оболочки.

Если реализация оболочки заключается в повторной вставке значения с использованием PriorityQueue'песок .add(...)методы, важно отметить, что .remove(...)бежит вовремя. В зависимости от реализации кучи обновление приоритета значения может быть выполнено в O(log n)или даже O(1)время, поэтому это предложение оболочки может не оправдать общих ожиданий.

Если вы хотите свести к минимуму свои усилия по реализации, а также риск появления ошибок любого кастомного решения, то обертка, выполняющая повторную вставку, выглядит просто и безопасно.

Если вы хотите, чтобы реализация была быстрее, чем O(n), то у вас есть несколько вариантов:

  1. Реализуйте кучу самостоятельно. Запись в Википедии описывает несколько вариантов с их свойствами. Этот подход, скорее всего, даст вам наилучшую производительность, в то же время, чем больше кода вы напишете сами, тем выше риск ошибок.

  2. Реализуйте другой тип оболочки: обработчик, обновляющий приоритет, помечая запись как удаленную, и добавляйте новую запись с измененным приоритетом. Это относительно легко сделать (меньше кода), см. ниже, хотя здесь есть свои оговорки.

Со второй идеей я столкнулся в документации Python и применил ее для реализации повторно используемой структуры данных в Java (см. предостережения внизу):

      public class UpdatableHeap<T> {

  private final PriorityQueue<Node<T>> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.priority));
  private final Map<T, Node<T>> entries = new HashMap<>();

  public void addOrUpdate(T value, int priority) {
    if (entries.containsKey(value)) {
      entries.remove(value).removed = true;
    }

    Node<T> node = new Node<>(value, priority);
    entries.put(value, node);
    pq.add(node);
  }

  public T pop() {
    while (!pq.isEmpty()) {
      Node<T> node = pq.poll();
      if (!node.removed) {
        entries.remove(node.value);
        return node.value;
      }
    }

    throw new IllegalStateException("pop from empty heap");
  }

  public boolean isEmpty() {
    return entries.isEmpty();
  }

  private static class Node<T> {
    private final T value;
    private final int priority;
    private boolean removed = false;

    private Node(T value, int priority) {
      this.value = value;
      this.priority = priority;
    }
  }
}

Обратите внимание на некоторые предостережения:

  • Записи, помеченные как удаленные, остаются в памяти до тех пор, пока они не будут извлечены.
    • Это может быть неприемлемо в случаях использования с очень частыми обновлениями.
  • Внутренняя обертка вокруг фактических значений — это дополнительные накладные расходы памяти (постоянные для каждой записи). Также есть внутренний Map, сопоставляя все значения, находящиеся в настоящее время в приоритетной очереди, с их Nodeобертка.
  • Поскольку значения используются на карте, пользователи должны знать об обычных предостережениях при использовании карты и убедиться, что они equalsа также hashCodeреализации.
Источник
Другие вопросы по тегам