From today, in Java: a user asked if changing the value of an item in a PriorityQueue would still result in the queue being correctly ordered. (He explained that he was doing this to prioritize based on counters, which makes sense. It’s worth noting that this blog entry is not about solving his problem, but about the behavior of PriorityQueue.)
Getting items out of a PriorityQueue requires peek() and/or poll(). Let’s take a look at some simple usage; first, let’s look at an object that represents something with a priority:

class Container implements Comparable {
  int x;
  public Container(int x) { this.x = x; }
  public int getX() { return x; }
  public void setX(int x) { this.x = x; }
  @Override
  public String toString() { return "Container{" + "x=" + x + '}'; }
  @Override
  public int compareTo(Container o) {
    return Integer.compare(getX(), o.getX());
  }
}

Let’s use this from another class. First, a utility method that builds a Queue, returning one element from the Queue for us to mutate later:

private static Container buildQueue(Queue q) {
  q.clear();
  q.add(new Container(4));
  q.add(new Container(2));
  q.add(new Container(6));
  Container c = new Container(5);
  q.add(c);
  return c;
}

As stated, we need to use peek() or poll() to get results out in correct order. If we use normal iteration, our order starts off correctly, but fails immediately. Here’s the code:

buildQueue(q);
for(Container c1:q) {
  System.out.println(c1);
}

And the output is:

Container{x=2}
Container{x=4}
Container{x=6}
Container{x=5}

The first element is in the right place – we expect 2 as the highest priority – but the others are in insertion order, not actual priority order.
If, however, we use poll(), we get different results. The code:

buildQueue(q);
while((c=q.poll())!=null) {
  System.out.println(c);
}

And the output:

Container{x=2}
Container{x=4}
Container{x=5}
Container{x=6}

What poll() does is simple: it removes the head of the Queue – the item with priority – and then it sifts the queue, with the result that the Queue‘s order is adjusted. Depending on the nature of the queue, this may put it in proper order all the way through the queue, but this is not required — the actual result is that the Queue is more ordered, with the new head of the Queue (the result of the next poll() or peek()) being set properly.

If you want to see the actual code for this process, grepcode has it: see PriorityQueue.poll(). Internally, “sift” is the actual term used.

Mutating the Elements in the Queue

What happens if we mutate the priority, then?
As it turns out, the behavior of the Queue doesn’t change much – except that the results of the last sifting of the Queue are maintained. This is actually a big deal. poll() doesn’t sift the Queue before returning the head of the queue. Therefore, if this is our code:

Container container = buildQueue(q);
System.out.println("1: "+q);
container.setX(3);
System.out.println("2: "+q);
while((c=q.poll())!=null) {
  System.out.println(c);
}

1: [Container{x=2}, Container{x=4}, Container{x=6}, Container{x=5}]
2: [Container{x=2}, Container{x=4}, Container{x=6}, Container{x=3}]
Container{x=2}
Container{x=3}
Container{x=4}
Container{x=6}

Note what happens: we modify the last element in the Queue to be 3, and the Queue maintains its order, but pulling the results out via poll() gives us the results as we expect. But if we change the priority of the last element such that it should be first… let’s see what that looks like.

container = buildQueue(q);
System.out.println("1: "+q);
container.setX(1);
System.out.println("2: "+q);
while((c=q.poll())!=null) {
  System.out.println(c);
}

Our output is:

1: [Container{x=2}, Container{x=4}, Container{x=6}, Container{x=5}]
2: [Container{x=2}, Container{x=4}, Container{x=6}, Container{x=1}]
Container{x=2}
Container{x=1}
Container{x=4}
Container{x=6}

Summary

As stated, PriorityQueue sifts its values after pulling the top element from the Queue. It’d be unwise to expect a Queue to work properly with mutable items in any case – much as using mutable keys in a Map would be unwise – but as you can see, mutating the priorities can work but can also fail if you happen to modify the priorities such that the element at the head of the list should change.