2

I read documentation and everything i could find about PriorityQueue, but still don't get why output is so strange I mean I can't get a point of adding order, can anyone explain?

PriorityQueue<String> pq = new PriorityQueue<String>();
pq.offer("2"); 
System.out.println("add 2 : " + pq); 
pq.offer("4");
System.out.println("add 4 : " + pq);
System.out.println(pq.peek() + " ");
pq.offer("1");
System.out.println("offer 1 : " + pq);
pq.offer("3");
System.out.println("add 3 : " + pq);
pq.remove("1");
System.out.println("remove 1 : " + pq);

Output: 

add 2 : [2]
add 4 : [2, 4]            <- why 4 goes there
offer 1 : [1, 4, 2]       <- why 1 goes first
add 3 : [1, 3, 2, 4]      <- why reorder
remove 1 : [2, 3, 4]      <- again
Nikolas Papirniy
  • 333
  • 2
  • 9
  • 2
    The elements are in [heap order](https://en.wikipedia.org/wiki/Heap_%28data_structure%29). – Fred Foo Sep 11 '12 at 12:01
  • 1
    Something to consider is does `PriorityQueue` implement `toString` in such a was that it orders the values in the `String`. Since it appears that `toString` is implemented in `AbstractCollection`, I would suggest that it might not. Try using `poll` to get elements out in correct order. – John B Sep 11 '12 at 12:01
  • @JohnB From the AbstractCollection: " The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets ("[]")." If PriorityQueue isn't overriding that method itself, then there should be a guarantee that it's ordered (though not necessarily how you'd expect). – Anthony Grist Sep 11 '12 at 12:03
  • 2
    @AnthonyGrist: "The iterator does not return the elements in any particular order." http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html#iterator%28%29 – Fred Foo Sep 11 '12 at 12:04

3 Answers3

3

PriorityQueue only guarantees that the first element is the smallest.

A binary heap only guarantees in each sub-heab (sub-tree) the root is the smallest element.
The heap is actually a complete-tree (or an array representation of it). Whenever you insert an element that violates the condition (is smaller then the root), the old root is sifted down. this is done recursively over the heap.

This partial ordering allows fast and relatively cache-efficient (with array representation) data structure that can be used if you only need the min element at each point at time.

amit
  • 175,853
  • 27
  • 231
  • 333
2

PriorityQueue is a tree like structure which ensures that first element is the smallest. The order of other elements is not important, and is likely to be due to how the PQ balances the tree.

As @larsmans points out, this is known as min heap order

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
2

Java doc:

An unbounded priority queue based on a priority heap. 
The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. 
A priority queue does not permit null elements. 
A priority queue relying on natural ordering also does not permit insertion of 
non-comparable objects (doing so may result in ClassCastException).

Also says:

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

What you are outputting is the toString() method. And the output is due how that method iterates the tree. The same order as the Iterator.

ssedano
  • 8,322
  • 9
  • 60
  • 98