Internal sorting of PriorityQueue

Question

I'm not able to understand the internal sorting that is taking place in PriorityQueue:

import java.util.*;

public class TryME {
    public static void main(String args[]) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        q.add(3);
        System.out.print(q);
        System.out.print("");
        q.add(1);
        System.out.print(q);
        System.out.print("");
        q.add(9);
        System.out.print(q);
        System.out.print("");
        q.add(6);
        System.out.print(q);
        System.out.print("");
        q.add(2);
        System.out.print(q);
        System.out.print("");
    }
}

Output:

[3][1, 3][1, 3, 9][1, 3, 9, 6][1, 2, 9, 6, 3]

On what basis is this sorting taking place?

Answer 1

The priority queue is implemented as a heap, where all children for a specific node is of lower priority than it's parent, but not necessarily of it's siblings.

The elements are stored in the array (I suspect) as follows:

For each node, the children are stored in 2*pos and 2*pos+1. Thus, for [1, 2, 9, 6, 3]:

element 1 (value 1), children are 2 and 9.
element 2 (value 2), children are 6 and 3
element 3 (value 9), 4 (value 6) and 5 (value 3) have no children...

If you remove from the queue the parent node is replaced by one of the children with the highest priority, which again is replaced by one of its children, etc. (The operation is very optimal, only O(log n) running time) For example:

[1, 2, 9, 6, 3]
[2, 9, 6, 3]
[3, 9, 6]
[6, 9]
[6]

The list is very much sorted, it's only in a heap which is not that evident when printing it our as a list.

Answer 2

The javadoc says:

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

If you execute

while (!q.isEmpty()) {
    System.out.println(q.poll());
}

You'll see that the elements are indeed sorted correctly.

Answer 3

A PriorityQueue maintains things in order of priority. The first element you pull out is the highest priority. The likelhood is that this is implemented underneath using a heap data structure which provides the data in an order but without the full sorting (this allows more efficient insertion and deletion than resorting the contents each time).

As a consumer, the internal order is not important to you for a priority queue. You should just grab elements from it and be satisfied that they are the highest priority. The internals aren't something you should concern yourself with (see the Java doc that JB Nizet pointed out).

Answer 4

I haven't done anything in Java for the past 7 years, but most probably the ordering is some kind of heap.

However, as noted in other replies, how Java orders the elements internally shouldn't matter to you, you just want the elements to come out in the right order (i.e. lower/higher priority first).