Updating Java PriorityQueue when its elements change priority

Question

I'm trying to use a PriorityQueue to order objects using a Comparator.

This can be achieved easily, but the objects class variables (with which the comparator calculates priority) may change after the initial insertion. Most people have suggested the simple solution of removing the object, updating the values and reinserting it again, as this is when the priority queue's comparator is put into action.

Is there a better way other than just creating a wrapper class around the PriorityQueue to do this?

Boxcar

You might find this SO question useful: https://mcmap.net/q/27210/-priorityqueue-heap-update – Basset

Great thanks, I didn't see that question before. – Boxcar

Answer 1

You have to remove and re-insert, as the queue works by putting new elements in the appropriate position when they are inserted. This is much faster than the alternative of finding the highest-priority element every time you pull out of the queue. The drawback is that you cannot change the priority after the element has been inserted. A TreeMap has the same limitation (as does a HashMap, which also breaks when the hashcode of its elements changes after insertion).

If you want to write a wrapper, you can move the comparison code from enqueue to dequeue. You would not need to sort at enqueue time anymore (because the order it creates would not be reliable anyway if you allow changes).

But this will perform worse, and you want to synchronize on the queue if you change any of the priorities. Since you need to add synchronization code when updating priorities, you might as well just dequeue and enqueue (you need the reference to the queue in both cases).

Gamp

I see, so removing the object altering it and reinserting it IS the best option? – Boxcar

I believe so. Of course, this can only be done if the code doing the altering is aware of any queues the object is waiting in. – Gamp

Yes, this is the case in my case. – Boxcar

Removing from PQ is O(n), a faster solution is to-reimplement a fast heap like Fibonacci heap / binomial heap. Then when decreasing a key, you will be able to update the PQ. For this each node will have to get a pointer to its parent in order to percolate it up. Hard way, but faster. – Football

Answer 2

I don't know if there is a Java implementation, but if you're changing key values alot, you can use a Fibonnaci heap, which has O(1) amortized cost to decrease a key value of an entry in the heap, rather than O(log(n)) as in an ordinary heap.

Squeeze

The JDK does not have a FibonacciHeap although it does exist from a third party. I know that once an object is added to my queue, it can only increase in priority, so does anyone know of an implementation with O(1) to swap two elements? such as the decrease functionality. Or can this be achieved easily with any implementation by swapping elements instead of with the PriorityQueue deleting and reinserting which would take O(1) and O(log(n)) respectively? – Boxcar

@MarcusWhybrow The Fibonnaci heap has constant amortized cost to decrease a key, but the constant in reality seems to be rather large. Your dataset have to be really large to make O(log n) worse than that constant. See Is there a standard Java implementation of a Fibonacci heap?. – Otten

Answer 3

One easy solution that you can implement is by just adding that element again into the priority queue. It will not change the way you extract the elements although it will consume more space but that also won't be too much to effect your running time.

To proof this let's consider dijkstra algorithm below

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;

}

Here our interest is in line pQueue.add(new Node(neighbour.destination, distance[neighbour.destination])); I am not changing priority of the particular node by removing it and adding again rather I am just adding new node with same value but different priority. Now at the time of extracting I will always get this node first because I have implemented min heap here and the node with value greater than this (less priority) always be extracted afterwards and in this way all neighboring nodes will already be relaxed when less prior element will be extracted.

Farther

You overflow with Integer.MAX_VALUE – Revamp

Answer 4

Without reimplementing the priority queue yourself (so by only using utils.PriorityQueue) you have essentially two main approaches:

1) Remove and put back

Remove element then put it back with new priority. This is explained in the answers above. Removing an element is O(n) so this approach is quite slow.

2) Use a Map and keep stale items in the queue

Keep a HashMap of item -> priority. The keys of the map are the items (without their priority) and the values of the map are the priorities.

Keep it in sync with the PriorityQueue (i.e. every time you add or remove an item from the Queue, update the Map accordingly).

Now when you need to change the priority of an item, simply add the same item to the queue with a different priority (and update the map of course). When you poll an item from the queue, check if its priority is the same than in your map. If not, then ditch it and poll again.

If you don't need to change the priorities too often, this second approach is faster. Your heap will be larger and you might need to poll more times, but you don't need to find your item. The 'change priority' operation would be O(f(n)log n*), with f(n) the number of 'change priority' operation per item and n* the actual size of your heap (which is n*f(n)).

I believe that if f(n) is O(n/logn)(for example f(n) = O(sqrt(n)), this is faster than the first approach.

Note : in the explanation above, by priority I means all the variables that are used in your Comparator. Also your item need to implement equals and hashcode, and both methods shouldn't use the priority variables.

Dropforge

Answer 5

It depends a lot on whether you have direct control of when the values change.

If you know when the values change, you can either remove and reinsert (which in fact is fairly expensive, as removing requires a linear scan over the heap!). Furthermore, you can use an UpdatableHeap structure (not in stock java though) for this situation. Essentially, that is a heap that tracks the position of elements in a hashmap. This way, when the priority of an element changes, it can repair the heap. Third, you can look for an Fibonacci heap which does the same.

Depending on your update rate, a linear scan / quicksort / QuickSelect each time might also work. In particular if you have much more updates than pulls, this is the way to go. QuickSelect is probably best if you have batches of update and then batches of pull opertions.

Magritte

Answer 6

To trigger reheapify try this:

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

Wiredraw

Why this will not create an infinite loop? – Reminiscence

@MohammadZulfikar This isn't a loop, it's just an if statement. It will perform two operations: remove and add. – Ambassadress

@MilesHenrichs Oh yeah! Sorry my bad. In that case it seems to be really good. What say? – Reminiscence

This is wrong as after the update there is no guarantee that the heap property was not broken and your answer essentially tries to re-heapify an array that may not have the heap property – Weaponless

@Weaponless is right. I've experienced it today. – Incombustible

Answer 7

Something I've tried and it works so far, is peeking to see if the reference to the object you're changing is the same as the head of the PriorityQueue, if it is, then you poll(), change then re-insert; else you can change without polling because when the head is polled, then the heap is heapified anyways.

DOWNSIDE: This changes the priority for Objects with the same Priority.

Hannahannah

Answer 8

Is there a better way other than just creating a wrapper class around the PriorityQueue to do this?

It depends on the definition of "better" and the implementation of the wrapper.

If the implementation of the wrapper is to re-insert the value using the PriorityQueue's .remove(...) and .add(...) methods, it's important to point out that .remove(...) runs in O(n) time. Depending on the heap implementation, updating the priority of a value can be done in O(log n) or even O(1) time, therefore this wrapper suggestion may fall short of common expectations.

If you want to minimize your effort to implement, as well as the risk of bugs of any custom solution, then a wrapper that performs re-insert looks easy and safe.

If you want the implementation to be faster than O(n), then you have some options:

1. Implement a heap yourself. The wikipedia entry describes multiple variants with their properties. This approach is likely to get your the best performance, at the same time the more code you write yourself, the greater the risk of bugs.

2. Implement a different kind of wrapper: handlee updating the priority by marking the entry as removed, and add a new entry with the revised priority. This is relatively easy to do (less code), see below, though it has its own caveats.

I came across the second idea in Python's documentation, and applied it to implement a reusable data structure in Java (see caveats at the bottom):

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;
    }
  }
}

Note some caveats:

• Entries marked removed stay in memory until they are popped
  • This can be unacceptable in use cases with very frequent updates
• The internal Node wrapped around the actual values is an extra memory overhead (constant per entry). There is also an internal Map, mapping all the values currently in the priority queue to their Node wrapper.
• Since the values are used in a map, users must be aware of the usual cautions when using a map, and make sure to have appropriate equals and hashCode implementations.

Practically