Is Java's PriorityQueue Instable or Nondeterministic or both?

Question

I was running through Java's documentation for its PriorityQueue and ran across an important note:

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

I would like to understand the actual meaning of that bolded word. The two properties I am interested in are PriorityQueue's Stability and its Determinism.

As far as I understand, a stable algorithm will (From wikipedia):

preserve the original order of the input set

Whereas a deterministic algorithm will (From wikipedia):

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

Here is my example:

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

For me, this code outputs the following:

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

If I switch the insertion order of Fred and James I get the same result; therefore the PriorityQueue is not stable. However, I cannot disprove its determinism. No matter what insertion order I try, no matter how many times I run the code, Fred always comes before James.

However, I am concerned that this behavior is computer or JVM specific (which in my mind would make it nondeterministic), or that there exists some counter example whereby the output will differ.

Another possibility is that although the implementation on all JVMs and Computers for now might be deterministic, this property is unspecified and subject to change at some point in the future.

I could understand if the internal implementation is breaking the tie based on some sort of ObjectID or internal memory value, this would make it unstable but deterministic. However, it could also be doing it based on system time, a random number, phases of the moon etc. This would make it both unstable and nondeterministic.

TLDR: Is Java's PriorityQueue Deterministic?

This question, despite its title, proves the algorithm's instability and its answer merely links to the documentation which doesn't answer to its determinism.

Answer 1

It is not stable: it can't be if ties are broken arbitrarily. This means that the implementation is free to choose whichever of the tied elements it wants to return first. A stable implementation would have to return tied elements in the order they are inserted into the queue.

It is not necessarily either deterministic or non-deterministic: it can choose how to break the tie arbitrarily, so it can either do this in a deterministic way (i.e. if you put in the same elements, you get them out in the same order, whatever that order is) or a non-deterministic way (i.e. the same elements don't come out in the same order).

Answer 2

While the Javadoc leaves room for interpretation, the Open-JDK implementation does not:

According to the source,offer(E e) adds the element at the end of the queue (increasing its size if necessary), and then calls private void siftUp(int k, E x) whose Javadoc says the following:

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.

So the implementation is completely deterministic, and depends on the comparator and the insertion order.

But since this appears to be an implementation detail, and your code relies on a specific order of elements, the you really shouldn't rely on it, and have your Comparator always return different values to avoid any tie-breaking.