Why do I get the following result? [duplicate]

Question

I have done the following test to see how a

PriorityBlockingQueue<String> pq = new PriorityBlockingQueue<>(2);
     pq.put("Sing");
     pq.put("Sing2");
     pq.put("Sing3");
     pq.put("Sing4");
     pq.put("Sing10");
     pq.put("Sing11");
     pq.put("Sing12");
     pq.put("Sing13");
     for (String s1: pq)
     {
         System.out.print(s1 +" ");
     }

The result I get is:

 Sing Sing10 Sing11 Sing13 Sing2 Sing3 Sing12 Sing4

Now how the API says it should order them in their natural order if no comparator specified at construction time. Hoever as you can see the result is not ordered at all.

Secondly the initial capacity I set was of 2, why there is such an option if the bound is actually not set? What's the point? I understand that the api specify that it's an unbounded priority queue however why making a constructor taking an initial capacity at all if it cannot set any bound of it?

So basically I have got 2 questions:

1) Why the order of the result above posted does not follow the natural order of the elements?

2) What is the purpose of having a constructor with a parameter "initial capacity" which does not actually set the bound. In the LinkedBlockingQueue it's reasonable as it sets the bound however it does not happen in the PriorityBlockingQueue.

Thanks in advance.

Answer 1

The order is guaranteed when you access the head with poll, remove, peek or take for example, but not when you iterate:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

This will yield the expected output:

String s;
while ((s = pq.poll()) != null) {
    System.out.println(s);
}

outputs:

Sing
Sing10
Sing11
Sing12
Sing13
Sing2
Sing3
Sing4

---

What is the purpose of having a constructor with a parameter "initial capacity" which does not actually set the bound.

The initial capacity is not a bound. The queue is backed by an array - by setting the initial capacity you can avoid unnecessary array resizing (similarly to ArrayList's constructor).

Answer 2

The javadoc says:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityBlockingQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

You will get elements in order when using peek()/poll()/take(). But not when iterating.

To answer your second question: the queue is implemented as an array of objects internally. Setting an initial capacity allows avoiding too many array copies when the queue grows and the number of elements exceeds the capacity. Just like an ArrayList.