CODEWITHSUNDEEP
javapriority-queue
Programming Noob
Programming Noob

Reputation: 1845

Simple Java PriorityQueue<String> error

All I am doing is add three strings to a Java PriorityQueue and then print them out This is my code:

import java.util.*;
import java.lang.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        PriorityQueue<String> pq=new PriorityQueue<String>();
        pq.add("abc");
        pq.add("ability");
        pq.add("aberdeen");

        String s="ability";
        System.out.println(s.compareTo("aberdeen"));

        System.out.println(pq);
    }
}

And this is the output:

4
[abc, ability, aberdeen]

Shouldn't this be abc, aberdeen, ability instead. since that's the correct alphabetic order?

Upvotes: 7

Views: 6764

Answers (2)

Marko Topolnik
Marko Topolnik

Reputation: 200168

The queue works properly. Run this code:

PriorityQueue<String> pq=new PriorityQueue<String>();
pq.add("abc");
pq.add("ability");
pq.add("aberdeen");
System.out.println(pq);
for (String s; (s = pq.poll()) != null;) System.out.println(s);

It will print

[abc, ability, aberdeen]
abc
aberdeen
ability

The reason lies with the fact that the priority semantics apply only to the dequeue operation, whereas in other respects the queue is bound only by the contract of the plain java.util.Collection: its iterator is not required to observe any particular order, and specifically, PriorityQueue's iterator happens to observe the insertion order.

Upvotes: 5

Jon Skeet
Jon Skeet

Reputation: 1500595

From the documentation of PriorityQueue.iterator():

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

That's what toString() is using to construct the string representation, as the implementation is inherited from AbstractCollection:

Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets ("[]"). [...]

Try dequeuing the results instead, and you'll get the expected order:

while (pq.size() > 0) {
    System.out.println(pq.poll());
}

Output:

abc
aberdeen
ability

Upvotes: 12

Related Questions