Обновление Java PriorityQueue при изменении приоритета его элементов

Вы должны удалить и снова вставить, поскольку очередь работает, помещая новые элементы в соответствующие позиции, когда они вставляются. Это намного быстрее, чем альтернатива поиска элемента с наивысшим приоритетом каждый раз, когда вы выходите из очереди. Недостатком является то, что вы не можете изменить приоритет после того, как элемент был вставлен. У 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]));. Я не изменяю приоритет конкретного узла, удаляя его и добавляя снова, а просто добавляю новый узел с тем же значением, но с другим приоритетом. Теперь во время извлечения я всегда буду получать этот узел первым, потому что я реализовал здесь минимальную кучу, а узел со значением больше, чем это (с меньшим приоритетом), всегда будет извлекаться впоследствии, и таким образом все соседние узлы уже будут расслаблены, когда меньше предыдущего элемент будет извлечен.

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

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

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

Чтобы запустить reheapify, попробуйте следующее:

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

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

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

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

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

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

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

Оставьте HashMap элемента - ›приоритет. Ключи карты - это элементы (без их приоритета), а значения карты - это приоритеты.

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

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

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

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

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