Priority queue

[amarkirt saroay]

Can anyone explain me the output for priority queue?
I am not able get why the first output gives result in sorted order? It should display numbers in insertion order(1,5,3,7,6,9,8).

Please explain !

import java.util.*;
class PQ {
static class PQsort
implements Comparator<Integer> { // inverse sort
public int compare(Integer one, Integer two) {
return two - one; // unboxing
}
}
public static void main(String[] args) {
int[] ia = {1,5,3,7,6,9,8 }; // unordered data
PriorityQueue<Integer> pq1 =
new PriorityQueue<Integer>(); // use natural order
for(int x : ia) // load queue
pq1.offer(x);
for(int x : ia) // review queue
System.out.print(pq1.poll() + " ");
System.out.println("");
PQsort pqs = new PQsort(); // get a Comparator
PriorityQueue<Integer> pq2 =
new PriorityQueue<Integer>(10,pqs); // use Comparator
for(int x : ia) // load queue
pq2.offer(x);
System.out.println("size " + pq2.size());
System.out.println("peek " + pq2.peek());
System.out.println("size " + pq2.size());
System.out.println("poll " + pq2.poll());
System.out.println("size " + pq2.size());
for(int x : ia) // review queue
System.out.print(pq2.poll() + " ");
}
}
This code produces something like this:
1 3 5 6 7 8 9
size 7
peek 9
size 7
poll 9
size 6
8 7 6 5 3 1 null

[ramesh maredu]

Please refer java doc for priority queue.

"Priority queue orders elements according to an order specified at construction time, which is specified either according to their natural order (see Comparable), or according to a Comparator".
[ July 22, 2008: Message edited by: ramesh maredu ]

[Raphael Rabadan]

Hello,

Priority Queue when we not use a Comparator uses the natural order, by natuaral order it means the Comparable the class implements, so Integer implements his comparable, and it is:

    /**
     * Compares two <code>Integer</code> objects numerically.
     *
     * @param   anotherInteger   the <code>Integer</code> to be compared.
     * @returnthe value <code>0</code> if this <code>Integer</code> is
     * equal to the argument <code>Integer</code>; a value less than
     * <code>0</code> if this <code>Integer</code> is numerically less
     * than the argument <code>Integer</code>; and a value greater 
     * than <code>0</code> if this <code>Integer</code> is numerically
     *  greater than the argument <code>Integer</code> (signed
     *  comparison).
     * @since   1.2
     */
    public int compareTo(Integer anotherInteger) {
int thisVal = this.value;
int anotherVal = anotherInteger.value;
return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
    }

So the result is ok, take a look on this commented code:

 
import java.util.Comparator;
import java.util.PriorityQueue;
 
class PQueue01 {
static class PQsort implements Comparator<Integer> {
public int compare(Integer one, Integer two) {
return two - one;
}
}
 
public static void main(String[] args) {
int[] ia = { 1, 5, 3, 7, 6, 9, 8 };
PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>();
for (int x : ia)
pq1.offer(x); // insert the array in the Queue
for (int x : ia)
System.out.print(pq1.poll() + " ");  // returns 1 by 1
System.out.println("");
PQsort pqs = new PQsort();
PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(10, pqs); // Uses a reversed comparator
for (int x : ia)
pq2.offer(x); // insert the array in the queue, remember, will be reversed.

System.out.println("size " + pq2.size()); // returns 7
System.out.println("peek " + pq2.peek()); // returns 9
System.out.println("size " + pq2.size()); // returns 7
System.out.println("poll " + pq2.poll()); // returns 9
System.out.println("size " + pq2.size()); // returns 6
for (int x : ia)
System.out.print(pq2.poll() + " ");  // returns 8 7 6 5 3 1 null(null because the queue has 1 less element, and it being iterated by the array length. 
 
}
}

I hope it helps.

Kind Regards,
Raphael Rabadan