Priority queue is not maintaining sorting order Am i implementing Comparable not properly? Wrong sorting order is coming as output?
import java.util.PriorityQueue;
class A implements Comparable
{
int i;
A(int i)
{
this.i = i;
}
public int compareTo(Object obj)
{
return i - ((A)obj).i;
}
public String toString()
{
return Integer.toString(i);
}
}
class Manager11
{
public static void main(String[] args)
{
PriorityQueue pq = new PriorityQueue();
pq.add(new A(9));
pq.add(new A(5));
pq.add(new A(8));
pq.add(new A(19));
pq.add(new A(1));
System.out.println(pq);
}
}
Output : [1, 5, 8, 19, 9]
In a priority queue, the only guarantee you have is that the head is the lowest (or greatest, depending on your comparison). The internal structure is not necessarily a sorted list. Actually, in Java, it's a heap:
PriorityQueue
An unbounded priority queue based on a priority heap.
However, if you do a loop that poll()
the first item, then print it, again and again until the priority queue is empty. The elements should be printed from the lowest to the greatest element.