This is because PriorityQueue is an implementation of min heap (in Java by default), this means the root element will be always lower than the other elements in the list.
To take the example from your question:
- When you insert 10, in the array the element at index 1 is 10
- When you insert 1, as
1 < 10
the element at position 1 is now 1 and 10 it shifted to index 2
- When you insert 2, as
1 < 2
there is no need to shift the element, and 2 is inserted at index 3
- When you insert 2, the 2 will go under 10, as
10 > 2
a shift is needed, 2 is inserted at 2 and 10 is shited to the index 4
After all inserts the array looks like this, also check the video below:
array: [NULL, 1, 2, 2, 10]
Now when you remove 2, a shift is required for 10, and 10 is moved back to index 2, and the state of array is [NULL, 1, 10, 2]
and this is what you see as the output when you iterate. Also, check the following method that is implemented inside PriorityQueue and is used when you don't provide a Comparator
.
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
PriorityQueue
is essentially a heap/tree structure. Iterating that array (which is how the enhanced for-each evaluates here) will iterate the elements in order of their storage, not of how they're traversed over the heap. So to the average person, it's essentially an "unordered" array. But that does not mean the queue-related methods (like#poll
, see below) are unordered.