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 ofthose 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;}@Overridepublic 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.

  • "given a particular input, [...] produce the same output" I would argue that changing the order of input items makes it not the same input. There are 120 different permutations of five items. I suspect that you could find at least one input order in which James will come before Fred.– Jim MischelFeb 19 at 13:30

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

  • I thought this might be the case: a third option being that its determinism is unspecified. Is there any clearer language in the documentation backing this up?– code11Feb 14 at 21:58
  • @code11 no, it is not specified. The implementation is free to choose.– Andy TurnerFeb 14 at 22:28

From the Java Doc:

The elements of the priority queue are ordered according to theirnatural ordering, or by a Comparator provided at queue constructiontime

So it depends on how you've defined the ordering in your comparator, or in the compareTo method of Herp (if it implements Comparable).

Want to make it deterministic? Write a comparator that breaks ties using a secondary property. Maybe the text of the name of the Herp object.

    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 promotingx up the tree until it is greater than or equal to its parent, or isthe 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.

      I believe there should be some mistake. PriorityQueue does not use X-rays to arrange items. So, if items are equal, then the final order should depend on the insertion order. That is my results:

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

      Actually, the order is deterministic. But it differs from the insertion order. And history of queue modifications is important too. But there is no any kind of random generator there.

        Your Answer


        By posting your answer, you agree to the privacy policy and terms of service.

        Not the answer you're looking for? Browse other questions tagged or ask your own question.