CODEWITHSUNDEEP
javacollections
Swapnil
Swapnil

Reputation: 137

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]

Upvotes: 5

Views: 4941

Answers (3)

Maxime Chéramy
Maxime Chéramy

Reputation: 18831

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.

Upvotes: 11

Andy Turner
Andy Turner

Reputation: 140326

You are not implementing Comparable correctly: it is a generic class, so you should specify the type parameters. I imagine you want Comparable<A>.

class A implements Comparable<A> {
  // ...

  @Override public int compare(A other) {
    return i - other.i;  // Cast is no longer required.
  }

  // ...
}

This will not change the output of your code, it will just get rid of the casts and warnings.

Additionally, don't compare ints using subtraction, as this doesn't handle overflows: use Integer.compare:

return Integer.compare(i, other.i);

Upvotes: 3

Amit Bera
Amit Bera

Reputation: 7325

Priory queue does not guarantee the ordering. The internal data structure it uses is Heap. But whenever you poll it returns the element in its priority order. For example below code :

for (int i = 0; i < 5; i++) {
    System.out.print(pq.poll() + " ,");
}

Gives you the output:

1 ,5 ,8 ,9 ,19

Upvotes: 4

Related Questions