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.

Answer 2

When you call System.out.print() on your PriorityQueue, it will not poll() your elements from it, but call toString(). PriorityQueue doesn't implement toString(), so it's the toString() from AbstractCollection which will be called:

public String toString() {
    Iterator<E> i = iterator();
if (! i.hasNext())
    return "[]";

StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
    E e = i.next();
    sb.append(e == this ? "(this Collection)" : e);
    if (! i.hasNext())
    return sb.append(']').toString();
    sb.append(", ");
}
}

As you can see, this method only iterate the PriorityQueue. As you can see in the PriorityQueue javadoc:

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 want to use the PriorityQueue as it is intented to be used, you have to poll() each value and print it:

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

Output:

2
4
6
8

Answer 3

That's because java.util.PriorityQueue implements a binary heap.

Unfortunately, there is no easy way to sort a PriorityQueue. If you poll() objects until the queue is empty, the elements will be in the comparator's order. That's why when I was faced with a similar problem I've implemented my own heap class that allows me to sort the elements after the fact; which I use for a top N list of a large number of elements.

(Since I made the class on the job, I don't have the right to post it here, but it's largely modeled after python's heap.py, so there's a good source of inspiration)

Answer 4

An unbounded priority queue is based on a priority heap

Priority Queue.Offer() method uses siftUpComparable() internally to insert items when passed without comparator

siftUpComparable compares current element with all elements at Parent Positions(int i = paramInt - 1 >>> 1;) until the Heap condition is met

---

siftUpComparable Algorithm in Nutshell (if implemented through array Root=index 0):

1.Add the element to the bottom level of the heap.
2.Compare the added element with its parent; if they are in the correct order, stop.
3.If not, swap the element with its parent and return to the previous step.

Java Code

  private void siftUpComparable(int paramInt, E paramE)
  {
    Comparable localComparable = (Comparable)paramE;
    while (paramInt > 0)
    {
      int i = paramInt - 1 >>> 1;
      Object localObject = this.queue[i];
      if (localComparable.compareTo(localObject) >= 0) {
        break;
      }
      this.queue[paramInt] = localObject;
      paramInt = i;
    }
    this.queue[paramInt] = localComparable;
  }

---

In Your example:

q.offer(4); -> Inserts 4

Result: PQ[0]=4

---

q.offer(2); -> siftUpComparable compares 4 to 2 and swap positions (comparisons at Parent Locations)

Result: PQ[0]=2,PQ[1]=4

---

q.offer(8); -> siftUpComparable Compares 8 and 2 (since 2 is at Parent Location)

Result: PQ[2]=8

---

q.offer(6);: -> siftUp Compares 6 with 4 (Parent of location 3 is Location 1 according to paramInt - 1 >>> 1; logic )

Result: PQ[3]=6

---

Final PQ=[2, 4, 8, 6]

Answer 5

How java priority Queue is suppose to work?

Basically your print statement does not traverse the tree in order.