PriorityQueue did not order its content correctly?

Question

The Java Doc says: Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

but when I write some test like this:

public class Test {

    public static void main (String a[]) {
        Queue<Integer> queue = new PriorityQueue<Integer>();

        for (int i = 1; i <= 20; i++) {
            queue.offer(i);
        }

        System.out.println(queue);

        Queue<Integer> queue2 = new PriorityQueue<Integer>();

        for (int i = 20; i >= 1; i--) {
            queue2.offer(i);
        }

        System.out.println(queue2);
    }
}

I got following output:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[1, 2, 7, 4, 3, 10, 8, 11, 5, 12, 13, 19, 15, 16, 9, 20, 14, 17, 6, 18]

Seenm like two queue with the same content, their content did not get same order?

http://stackoverflow.com/questions/10972459/strange-ordering-in-priorityqueue-in-java?rq=1 — , Nov 06 '13 at 01:21

G. Bach · Accepted Answer · 2013-11-06T01:21:56.797

6

A priority queue gives no guarantee with regard to the ordering of the complete set; all it guarantees is that the smallest element is at the front (or the largest, if it's a max priority queue).

From the docs:

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()).

Maybe to add a little context: what a priority queue does internally is store the elements in a tree structure of logarithmic height (in the sensible implementations using trees anyway). The insert and remove-like operations are designed to keep the smallest element at the root of that tree and to keep the elements in each subtree larger than the element of the parent vertex (that's what makes them heaps, that property is called the heap property). It does not guarantee any ordering on the elements of subtrees that are siblings as we know it for example from sort trees. The heap property together with the logarithmic height is what gives priority queues their fast operation runtimes, but it comes with the downside that you'll only ever get one element quickly, and that's the smallest one (or largest one for max heaps).

edited Nov 06 '13 at 01:21

answered Nov 06 '13 at 01:13

G. Bach

3,869
2
25
46

(therefore, if you `poll()` the `queue2` instance repeatedly, you'll get the elements sorted) – Petr Janeček Nov 06 '13 at 01:15
Just to add a little color here, Java's priority queue implementation is based on a priority heap. One can better understand the behavior of a priority queue by reading up on heaps. http://en.wikipedia.org/wiki/Heap_(data_structure) – Nov 06 '13 at 01:16
@Slanec: Yes, that will be sorted then, and that procedure is sometimes called `HeapSort`, deriving from the fact that priority queues usually are implemented as heaps with some ordering invariant. – G. Bach Nov 06 '13 at 01:17
Very aprreicate for your explaination. Seems like When **offer()** the item from 1 to 20 cunstructed a tree which is diff from the one constructed reversly. I would take some study to see the wiki page you post there. Thanks again, guys. – Terry Zhao Nov 06 '13 at 12:41

score 0 · Answer 2 · answered Nov 06 '13 at 02:58

0

PriorityQueue.toString uses iterator() which is not guaranteed to traverse the elements of the priority queue in any particular order (from API). Try

    while(!queue.isEmpty()) {
            System.out.print(queue.poll() + ",");
    }

answered Nov 06 '13 at 02:58

Evgeniy Dorofeev

133,369
30
199
275

PriorityQueue did not order its content correctly?

2 Answers2