PriorityQueue internal sorting

Question

I cannot understand the internal sorting that happens 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 does this sorting take place?

Answer 1

The javadoc says:

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

If you follow

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

You will see that the items are indeed sorted correctly.

Answer 2

A PriorityQueue keeps things in order of priority. The first item you pull is the highest priority. The likelihood is that this is implemented using the heap data structure , which provides the data in order, but without full sorting (this allows for more efficient input and deletion than accessing the contents each time).

As a consumer, internal order is not important to you in the priority queue. You just have to grab the elements from it and be sure that they are the highest priority. Internals are not something you should care about (see the Java Document that JB Nizet pointed out).

Answer 3

The priority queue is implemented as a heap, where all the children for a particular node have a lower priority than the parent, but not necessarily from his siblings.

Elements are stored in an 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... 

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

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

The list is very sorted, it is only on the heap, which is not so obvious when printing it as a list.

Answer 4

I have not done anything in Java over the past 7 years, but most likely ordering is a kind of heap .

However, as noted in other answers, how Java orders elements within itself does not matter to you, you just want the elements to come out in the correct order (i.e., first with a lower priority).

Answer 5

Basically, it is not sorted. Priority queue implementations usually amortize the cost of sorting — they perform the minimum effort necessary to ensure that items are received in the correct order. It is partially sorted each time an item is extracted enough to select the item with the highest priority. The queue is never completely sorted.

Instead of printing the entire queue, if you call poll() to extract the numbers, you will get them back in the expected order.