为什么优先级队列中的键应该是不可变的

Question

我正在coursea.org上研究Robert Sedgewick的算法。他提到，对于优先级队列，密钥应该是不可变的？为什么？

Answer 1

以下是的简单示例

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

你会得到类似的输出

10
20
30

40
20
30

请注意，在第二次删除中，它首先删除了40。但人们的期望是它应该最后被移除。因为当它添加时，它有10个元素，这被认为是第一个元素。

然而，如果您将另一个元素添加到同一个队列中，它就会正确地重新排序。

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

将作为

5
20
30
40

检查PriortyQueue的screenUpUsingComparator方法。

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

适用于其他托收吗？

好吧，这取决于集合，实现。例如：TreeSet属于同一类别。它只是保留/使用Comparator，而insert不迭代。

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

将导致

40
20
30

这也不例外。

Answer 2

PriorityQueue的键（条目）应该是不可变的原因是PriorityQueue无法检测到这些键的更改。例如，当您插入具有特定优先级的密钥时，它将被放置在队列中的某个位置。（实际上，在后台实现中，它更像是一棵"树"，但这在这里并不重要）。现在修改此对象时，其优先级可能会更改。但是它不会改变它在队列中的位置，因为队列不知道对象被修改了。该对象在队列中的位置可能只是错误的，队列将变得不一致（即，以错误的顺序返回对象）。

请注意，对象不必严格地完全不可变。重要的一点是，可能不会对对象进行影响其优先级的修改。修改优先级计算中涉及的而非的对象的字段是完全可行的。但必须小心，因为更改是否影响优先级可能会在相应条目的类别中明确指定，也可能不会。

Answer 3

这里有一个简单的例子，展示了它是如何中断的-第一个队列按预期顺序打印数字，但第二个队列没有，因为其中一个数字在添加到队列后发生了变异。

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
}