In a Java PriorityQueue, you can't decrease an element's priority by reinserting it

    Adam Dingle

Sometimes we may wish to decrease the priority of an existing element in a Java PriorityQueue. This is necessary, for example, in an implementation of Dijkstra's algorithm.

A popular and accepted answer on Stack Overflow states that you can efficiently decrease an element's priority by reinserting the element into the queue with a new, lower priority. The queue will still contain the element at the old, higher priority, but you can simply ignore that second instance of the element when you happen to remove it.

Unfortunately this technique is unsound: it may corrupt the queue and cause the remove() method to fail to remove the lowest element. Let's demonstrate this and see why it happens.

Suppose that a PriorityQueue holds objects of a class Node. Node has a custom compareTo method that compares using a priority stored in the instance variable prio:

import java.util.PriorityQueue;

class Node implements Comparable<Node> {
  public int prio;
  public Node(int prio) { this.prio = prio; }
  
  public int compareTo(Node n) {
    return Integer.compare(this.prio, n.prio);
  }
}

Now a PriorityQueue<Node> will order nodes by prio.

Suppose that n is an existing node in a PriorityQueue with prio = 10, and we wish to reduce its priority to 0. One way to accomplish this is to remove the element from the queue, modify its priority, and add it back:

q.remove(n);
n.prio = 0;
q.add(n);

This works correctly, but unfortunately the remove method runs in time O(N) when there are N elements in the priority queue. So it would be nice to have a faster way.

The Stack Overflow article mentioned above states that you can instead do this:

n.prio = 0;

q.add(n);

You will now have two copies of n in the queue. The claim is that as you remove items from the queue, you will first see n in its proper position at priority 0, and then later at priority 10. You can simply ignore the second instance of n as you remove it.

Unfortunately this simply doesn't work, as this program demonstrates:

class Test {
  public static void main(String[] args) {
    PriorityQueue<Node> q = new PriorityQueue<Node>();
    Node one = new Node(1);
    Node two = new Node(2);
    Node three = new Node(3);
    q.add(one);
    q.add(two);
    q.add(three);
    
    two.prio = 0;
    q.add(two);  // add the same element again
    System.out.println(q.remove().prio);
  }
}

When we run this program with OpenJDK 11.0.1, it prints

1

So the attempt to add the element again at priority 0 was not successful: it was not retrieved by remove(), which should always return the lowest value.

What's going on here? The proposed technique might work if Java's PriorityQueue implementation stored its own copy of each element's priority. But it doesn't work like that. PriorityQueue simply calls compareTo to compare elements, and lets elements worry about their own priorities.

In the program above, the underlying binary heap looks like this after we first insert the three Node objects:

Then after we execute

    two.prio = 0;

the heap looks like this:

This is no longer a valid heap: it violates the heap invariant, which says that every child must be greater than or equal to its parent.

And now after we add the same node again:

q.add(two);

the heap now looks like this:

The reinserted element with prio = 0 has failed to reach its proper place in the heap due to the invalid heap structure. And now remove() returns the element with priority 1.

So if you want to reduce an element's priority in a PriorityQueue, you really must remove it and reinsert it, which unfortunately takes O(N) time. If that's unacceptable, you'll need to use another collection class such as a TreeSet.