Why should keys in a priority queue be immutable?

Question

I'm looking at algorithms on coursea.org by Robert Sedgewick. He mentions that keys should be immutable for a priority queue? Why?

Answer 1

Here is simple Example

public static void main(String[] args)
    {
        Comparator<AtomicInteger> comparator = new AtomicIntegerComparater();
        PriorityQueue<AtomicInteger> queue =
                new PriorityQueue<AtomicInteger>(10, comparator);
        AtomicInteger lessInteger = new AtomicInteger(10);
        AtomicInteger middleInteger = new AtomicInteger(20);
        AtomicInteger maxInteger = new AtomicInteger(30);
        queue.add(lessInteger);
        queue.add(middleInteger);
        queue.add(maxInteger);
        while (queue.size() != 0)
        {
            System.out.println(queue.remove());
        }



        queue.add(lessInteger);
        queue.add(middleInteger);
        queue.add(maxInteger);

        lessInteger.addAndGet(30);
        while (queue.size() != 0)
        {
            System.out.println(queue.remove());
        }
    }
    }



class AtomicIntegerComparater implements Comparator<AtomicInteger>
{
    @Override
    public int compare(AtomicInteger x, AtomicInteger y)
    {

        if (x.get() < y.get())
        {
            return -1;
        }
        if (x.get() > y.get())
        {
            return 1;
        }
        return 0;
    }
}

You will get an output like

10
20
30


40
20
30

Note in the second removal , it removes 40 first. but the expectation is it should removed last. Since while it added it has 10 and that is considered as first element.

How ever, if you add another element to the same queue, it is re-ordering properly.

queue.add(lessInteger);
        queue.add(middleInteger);
        queue.add(maxInteger);
        lessInteger.addAndGet(30);
        queue.add(new AtomicInteger(5));
        while (queue.size() != 0)
        {
            System.out.println(queue.remove());
        }

would result as

5
20
30
40

Check siftUpUsingComparator method of PriortyQueue .

private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

is it applicable to other Collection ?

Well it depends upon the that Collection , Implementation. For example : TreeSet fall under same category. it just keeps / use the Comparator while insert not iterate.

TreeSet<AtomicInteger> treeSets = new TreeSet<AtomicInteger>(comparator);
        lessInteger.set(10);
        treeSets.add(middleInteger);
        treeSets.add(lessInteger);
        treeSets.add(maxInteger);
        lessInteger.addAndGet(30);
        for (Iterator<AtomicInteger> iterator = treeSets.iterator(); iterator.hasNext();) {
            AtomicInteger atomicInteger = iterator.next();
            System.out.println(atomicInteger);
        }

Would result in

40
20
30

Which is not excepted.

Answer 2

The reason why keys (entries) of a PriorityQueue should be immutable is that the PriorityQueue can not detect changes of these keys. For example, when you insert a key with a certain priority, it will be placed at a certain position in the queue. (Actually, in the backing implementation, it is more like a "tree", but this does not matter here). When you now modify this object, then its priority may change. But it will not change its position in the queue, because the queue does not know that the object was modified. The placement of this object in the queue may then simply be wrong, and the queue will become inconsistent (that is, return objects in the wrong order).

Note that the objects do not strictly have to be completely immutable. The important point is that there may be no modification of the objects that affects their priority. It's perfectly feasible to modify a field of the object that is not involved in the computation of the priority. But care has to be taken, because whether a change affects the priority may or may not be specified explicitly in the class of the respective entries.

Answer 3

Here is a simple example that shows how it breaks - the first queue prints numbers in order as expected but the second doesn't because one of the numbers has been mutated after having been added to the queue.

public static void main(String[] args) throws Exception {
    PriorityQueue<Integer> ok = new PriorityQueue<>(Arrays.asList(1, 2, 3));
    Integer i = null;
    while ((i = ok.poll()) != null) System.out.println(i); //1,2,3

    PriorityQueue<AtomicInteger> notOk = new PriorityQueue<>(Comparator.comparing(AtomicInteger::intValue));
    AtomicInteger one = new AtomicInteger(1);
    notOk.add(one);
    notOk.add(new AtomicInteger(2));
    notOk.add(new AtomicInteger(3));
    one.set(7);
    AtomicInteger ai = null;
    while ((ai = notOk.poll()) != null) System.out.println(ai); //7,2,3
}