Java 的 PriorityQueue 是不稳定的还是非确定性的，或者两者兼而有之？

Question

我正在运行浏览 Java 的 PriorityQueue 和运行文档，其中有一条重要说明：

If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily

我想了解那个粗体字的实际含义。我感兴趣的两个属性是 PriorityQueue 的稳定性和确定性。

据我了解，稳定的算法将（来自维基百科）：

preserve the original order of the input set

而确定性算法将（来自维基百科）：

given a particular input, [...] produce the same output

这是我的例子：

public class PriorityQueueTest {
    public static class Herp implements Comparable<Herp>{
        int attribute;
        String name;

        Herp(int attribute,String name){
            this.attribute=attribute;
            this.name=name;
        }
        @Override 
        public String toString(){
            return name+": "+attribute;
        }
        @Override
        public int compareTo(Herp o) {
            return Integer.compare(o.attribute, this.attribute);
        }

    }
    public static void main(String[] args){
            PriorityQueue<Herp> queue= new PriorityQueue<Herp>();
            queue.add(new Herp(1,"Fred"));
            queue.add(new Herp(1,"James"));
            queue.add(new Herp(2,"Bob"));
            queue.add(new Herp(3,"Rachel"));
            queue.add(new Herp(4,"Constance"));
            List<Herp> debug= new ArrayList<>();
            while(!queue.isEmpty()){
                debug.add(queue.poll());
            }
            System.out.println(Arrays.toString(debug.toArray()));
    }
}

对我来说，这段代码输出如下：

[Constance: 4, Rachel: 3, Bob: 2, Fred: 1, James: 1]

如果我调换 Fred 和 James 的插入顺序，我会得到相同的结果；因此 PriorityQueue 不稳定。但是，我无法反驳它的决定论。无论我尝试什么插入顺序，无论我运行代码多少次，Fred 总是排在 James 之前。

但是，我担心这种行为是特定于计算机或 JVM 的（在我看来这会使它具有不确定性），或者存在一些输出会有所不同的反例。

另一种可能性是，虽然目前在所有 JVM 和计算机上的实施可能是确定性的，但这个属性是未指定的，并且在将来的某个时候可能会发生变化。

我可以理解，如果内部实现基于某种 ObjectID 或内部内存值打破平局，这会使它不稳定但具有确定性。但是，它也可以根据系统时间、运行dom 数字、月相等来进行。这会使它既不稳定又不确定。

TLDR：Java 的 PriorityQueue 是确定性的吗？

，尽管它的标题证明了算法的不稳定性，它的答案只是链接到没有回答其确定性的文档。

Answer 1

来自 Java 文档：

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time

所以这取决于您如何在比较器中或在 Herp 的 compareTo 方法中定义顺序（如果它实现了 Comparable）。

想让它具有确定性吗？编写一个使用辅助属性打破平局的比较器。也许是 Herp 对象名称的文本。

Answer 2

虽然 Javadoc 留有解释空间，但 Open-JDK implementation 没有：

根据 source，offer(E e) 在队列末尾添加元素（必要时增加其大小），然后调用 private void siftUp(int k, E x)，其 Javadoc 说明如下：

Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root.

所以实现是完全确定的，并且取决于比较器和插入顺序。

但由于这似乎是一个实现细节，并且您的代码依赖于元素的特定顺序，因此您真的不应该依赖它，并且让您的 Comparator 始终 return不同的值以避免任何平局。

Answer 3

它不稳定：如果关系被任意打破，它就不可能稳定。这意味着实现可以自由选择它想要首先 return 的任何绑定元素。一个稳定的实现必须 return 按照元素插入队列的顺序绑定元素。

它不一定是确定性的或非确定性的：它可以任意选择如何打破平局，因此它可以以确定性的方式做到这一点（即，如果你放入相同的元素，你会把它们取出来以相同的顺序，无论该顺序是什么）或非确定性方式（即相同的元素不会以相同的顺序出现）。

Answer 4

我想应该是有误。 PriorityQueue 不使用 X 射线来排列项目。因此，如果项目相等，则最终顺序应取决于插入顺序。这是我的结果：

[Constance: 4, Rachel: 3, Bob: 2, Fred: 1, James: 1]
[Constance: 4, Rachel: 3, Bob: 2, James: 1, Fred: 1]

实际上，顺序是确定的。但它不同于插入顺序。队列修改的历史也很重要。但是那里没有任何类型的随机生成器。

Java 的 PriorityQueue 是不稳定的还是非确定性的，或者两者兼而有之？

Is Java's PriorityQueue Instable or Nondeterministic or both?

java

priority-queue

deterministic