javacollections

Priority queue is not maintaining sorting order


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]


Solution

  • 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.