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

Как вы обнаружили, приоритетная очередь не обрабатывает все элементы всякий раз, когда элемент добавляется или удаляется. Это было бы слишком дорого (помните нижнюю границу n log n для сортировки сравнения), в то время как любая разумная реализация очереди с приоритетом (включая PriorityQueue) обещает добавлять / удалять узлы в O (log n).

Фактически, он вообще не сортирует свои элементы (поэтому его итератор не может обещать перебирать элементы в отсортированном порядке).

PriorityQueue не предлагает API для информирования об измененном узле, так как это потребовало бы от него обеспечения эффективного поиска узлов, который его базовый алгоритм не поддерживает. Реализация приоритетной очереди, которая выполняет, довольно сложна. Хорошей отправной точкой для чтения об этом может быть статья в Википедии о PriorityQueues. Однако я не уверен, что такая реализация будет быстрее.

Простая идея - удалить, а затем добавить измененный узел. Не этого делать, поскольку remove() принимает O (n). Вместо этого вставьте другую запись для того же узла в PriorityQueue и игнорируйте дубликаты при опросе очереди, т.е. сделайте что-нибудь вроде:

PriorityQueue<Step> queue = new PriorityQueue();

void findShortestPath(Node start) {
    start.distance = 0;
    queue.addAll(start.steps());

    Step step;
    while ((step = queue.poll()) != null) {
        Node node = step.target;
        if (!node.reached) {
            node.reached = true;
            node.distance = step.distance;
            queue.addAll(node.steps());
        }
    }

}

Изменить: не рекомендуется изменять приоритеты элементов в PQ, поэтому необходимо вставлять Steps вместо Nodes.

вам придется удалить и снова вставить каждый редактируемый элемент. (собственно элемент, а не фиктивный!). Итак, каждый раз, когда вы обновляете distances, вам нужно удалять и добавлять элементы, на которые повлияло изменение Entree.

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

Недостатком Java PriorityQueue является то, что remove(Object) требует времени O (n), что приводит к времени O (n), если вы хотите обновить приоритеты, удаляя и снова добавляя элементы. Однако это можно сделать за время O (log (n)). Поскольку мне не удалось найти работающую реализацию через Google, я попытался реализовать ее сам (хотя на Kotlin, поскольку я действительно предпочитаю этот язык Java), используя TreeSet. Кажется, это работает, и для добавления / обновления / удаления должно быть O (log (n)) (обновление выполняется через add):

// update priority by adding element again (old occurrence is removed automatically)
class DynamicPriorityQueue<T>(isMaxQueue: Boolean = false) {

    private class MyComparator<A>(val queue: DynamicPriorityQueue<A>, isMaxQueue: Boolean) : Comparator<A> {
        val sign = if (isMaxQueue) -1 else 1

        override fun compare(o1: A, o2: A): Int {
            if (o1 == o2)
                return 0
            if (queue.priorities[o2]!! - queue.priorities[o1]!! < 0)
                return sign
            return -sign
        }

    }

    private val priorities = HashMap<T, Double>()
    private val treeSet = TreeSet<T>(MyComparator(this, isMaxQueue))

    val size: Int
        get() = treeSet.size

    fun isEmpty() = (size == 0)

    fun add(newElement: T, priority: Double) {
        if (newElement in priorities)
            treeSet.remove(newElement)
        priorities[newElement] = priority
        treeSet.add(newElement)
    }

    fun remove(element: T) {
        treeSet.remove(element)
        priorities.remove(element)
    }

    fun getPriorityOf(element: T): Double {
        return priorities[element]!!
    }


    fun first(): T = treeSet.first()
    fun poll(): T {
        val res = treeSet.pollFirst()
        priorities.remove(res)
        return res
    }

    fun pollWithPriority(): Pair<T, Double> {
        val res = treeSet.pollFirst()
        val priority = priorities[res]!!
        priorities.remove(res)
        return Pair(res, priority)
    }

}

Вы можете избежать обновления элементов в очереди, просто пометив каждый узел как посещенный = false по умолчанию и добавив новые элементы в очередь по мере продвижения.

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

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

Также, вероятно, будет проще, если вы отделите внутреннее устройство алгоритма от структуры данных графа.

public void dijkstra(Node source) throws Exception{
    PriorityQueue q = new PriorityQueue();
    source.work.distance = 0;
    q.add(new DijkstraHeapItem(source));

    while(!q.isEmpty()){
        Node n = ((DijkstraHeapItem)q.remove()).node;
        Work w = n.work;

        if(!w.visited){
            w.visited = true;

            Iterator<Edge> adiacents = n.getEdgesIterator();
            while(adiacents.hasNext()){
                Edge e = adiacents.next();
                if(e.weight<0) throw new Exception("Negative weight!!");
                Integer relaxed = e.weight + w.distance;

                Node t = e.to;
                if (t.work.previous == null || t.work.distance > relaxed){
                    t.work.distance = relaxed;
                    t.work.previous = n;
                    q.add(new DijkstraHeapItem(t));
                }
            }
        }
    }
}

Проблема в том, что вы обновляете массив distances, но не соответствующую запись в queue. Чтобы обновить соответствующие объекты в очереди, нужно удалить, а затем добавить.

Я решаю эту проблему, разделив свой процесс на временные интервалы (планировщик времени подойдет) и расширив собственный PriorityQueue. Поэтому я реализую метод уведомления, в котором ключом этого метода является следующий код:

// If queue has one or less elements, then it shouldn't need an ordering
// procedure
if (size() > 1)
{
    // holds the current size, as during this process the size will
    // be vary
    int tmpSize = size();
    for (int i = 1; i < tmpSize; i++)
    {
        add(poll());
    }
}

Надеюсь, это помогло.