Updating Java Priorityqueue When Its Elements Change Priority

Updating Java PriorityQueue when its elements change priority

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).

Changing the priority of an element in a PriorityQueue

Remove the object, change its priority, and re-add it to the queue.

My intuition is that the data structure doesn't normally watch the internal state of the objects and that it requires an add() or remove() operation to trigger a re-invocation of the comparator. A call to Collections.sort(), would also work, but you would have to transform the queue to a list and then back to a queue. This might make more sense if you change a lot of priorities at one time.

Better still, you might update n priorities, then add and remove the last one.

Updating Java PriorityQueue when its elements change priority

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).

Updating a PriorityQueue when iterating it

This code is in the Java 6 implementation of PriorityQueue:

private class Itr implements Iterator<E> {
  /**
   * The modCount value that the iterator believes that the backing
   * Queue should have.  If this expectation is violated, the iterator
   * has detected concurrent modification.
   */
  private int expectedModCount = modCount;

  public E next() {
    if(expectedModCount != modCount) {
      throw new ConcurrentModificationException();
    }

  }

}

Now, why is this code here? If you look at the Javadoc for ConcurrentModificationException you will find that the behaviour of an iterator is undefined if modification occurs to the underlying collection before iteration completes. As such, many of the collections implement this modCount mechanism.

To fix your code

You need to ensure that you don't modify the code mid-loop. If your code is single threaded (as it appears to be) then you can simply do as your coworker suggested and copy it into a list for later inclusion. Also, the use of the Iterator.remove() method is documented to prevent ConcurrentModificationExceptions. An example:

List<Entry> toAdd = new ArrayList<Entry>();
Iterator it = mEntries.iterator();
while(it.hasNext()) {
  Entry e = it.next();

  if(e.getId().equals(someId)) {
    Entry newEntry = e.setData(newData);
    it.remove();
    toAdd.add(newEntry);
  }
}
mEntries.addAll(toAdd);

PriorityQueue changes elements positions on poll()

PriorityQueue only claims to make the first entry in correct order. If you iterate over the PriorityQueue you can see all but the first element in any order and it may change as you add/remove entries.

From the Javadoc for PriorityQueue

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

If you need correct ordering at all times I suggest using TreeSet.

NavigableSet<MyType> orderedSeedQueue = new TreeSet<>(new MyComparator());
// add elements

while(!orderSeedQueue.isEmpty()) {
     firstItem = orderSeedQueue.pollFirst();

However, depending on your use case it may be simpler to sort them.

List<MyType> types = ...
Collections.sort(types, new MyComparator());
for(MyType t : types) { // in sorted order

---

Related Topics