Sorting Priority Queue in Java

Question

I was trying to insert the integers in PriorityQueue, and I know that :

If no comparator is specified when a PriorityQueue is constructed, then the default comparator for the type of data stored in the queue is used. The default comparator will order the queue in ascending order

However, the output I am getting is not in sorted order. Output after running the below code is : [2, 4, 8, 6]

public static void main(String args[]) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(10);
    q.offer(4);
    q.offer(2);
    q.offer(8);
    q.offer(6);

    System.out.print(q);
}

Can someone please explain why ?

Answer 1

A PriorityQueue is what is called a binary heap. It is only ordered/sorted in the sense that the first element is the least. In other word, it only cares about what is in the front of the queue, the rest are "ordered" when needed.

The elements are only ordered as they are dequeued, i.e. removed from the queue using poll(). This is the reason why a PriorityQueue manages to have such good performance, as it is not doing any more sorting than it needs at any time.

If you want to know how heaps work in detail I recommend this MIT lecture on heaps.