TreeXxx VS PriorityQueue

[Douglas Boff Nandi]

Hi all

I understand because the TreeSet return an sorted result. But I dont understand the result given by an iteraction with PriorityQueue. Can anyone help me with this.. please take the example:

import java.util.*;
public class Testetete {
	public static void main(String[] args) {
		TreeSet<String> t = new TreeSet<String>();
		t.add("a"); t.add("b"); t.add("d");t.add("c");t.add("zzz");
		t.add("f");t.add("e");t.add("i");t.add("g");t.add("aaa");t.add("z");
		show(t);

		Queue<String> q = new PriorityQueue<String>();
		q.add("a"); q.add("b"); q.add("d");q.add("c");q.add("zzz");
		q.add("f");q.add("e");q.add("i");q.add("g");q.add("aaa");q.add("z");
		show(q);
		
	}
	public static void show(Iterable t) {
		for(Object o:t){
			System.out.print(","+o);
		}
		System.out.println();
	}
}

This code give the following outputs:
,a,aaa,b,c,d,e,f,g,i,z,zzz
,a,aaa,d,c,b,f,e,i,g,zzz,z

I understood the first line of output, because its from a sorted set (TreeSet). But how about the second output (from PriorityQueue)? Can anyone help me?

Thank you all.

[Vijitha Kumara]

Java API wrote:
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

This would solve your problem .

[Douglas Boff Nandi]

Yeah! Its clear for me now!

Thank you Vijitha Kumara

[Ruben Soto]

Are you sure you understand what's going on? Because the answer, as it relates to the question, is a little confusing.

PriorityQueue is a sorted collection. If you instantiate a PriorityQueue without using a Comparator, then the sort order is established by the compareTo() method (which all elements inserted to the PriorityQueue must implement.) You can also use a Comparator by using the appropriate PriorityQueue constructor. In the case of String, which is the case in your example, String implements Comparable<String>, which will cause lexicographical ordering.

But: PriorityQueue inherits iterator() from Collection, and that method returns an Iterator which doesn't guarantee any specific ordering. Therefore, your second line of output is a fluke (you shouldn't rely on that order.) However, if you polled the queue sequentially, you would get the elements in the lexicographical sorted order in a reliable way.

[Douglas Boff Nandi]

Hi Ruben Soto

I understood the PriorityQueue is a sorted collection. And TreeSet are sorted collection too.

But the difference is in the implementation of iterator method,
used implicitly in for-each by the compiler.

    // TreeSet
    /**
     * Returns an iterator over the elements in this set in ascending order.
     */
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator(); 
// specific iterator, that return a sorted set 
// (implementation of this is at KeySet innerclass of TreeMap)
    }

    // PriorityQueue
    /**
     * Returns an iterator over the elements in this queue. The iterator
     * does not return the elements in any particular order.
     */
    public Iterator<E> iterator() {
        return new Itr(); 
// private final class Itr implements Iterator<E> (an innerclass)
    }

I'm sure? Thank you Ruben Soto

[Ruben Soto]

Douglas Boff Nandi wrote:
I'm sure? Thank you Ruben Soto

It sounds like I offended you, although I was trying to help you. The response talks about a behavior which was not exposed by the output that you offered.

EDIT: Nevermind, it seems I didn't pay attention to your second line of output.

Sorry for the confusion, Douglas Boff Nandi.

[Douglas Boff Nandi]

I m sorry.. its a problem caused because I am not so good with English language! Im from Brazil and I speak portuguese here.

I only asked to you if my reasoning is correctly.

Don't worry, Of course you helped me!

[Ruben Soto]

Douglas Boff Nandi wrote:I m sorry.. its a problem caused because I am not so good with English language! Im from Brazil and I speak portuguese here.

I only asked to you if my reasoning is correctly.

Don't worry, Of course you helped me!

Well, Vijitha did all the helping. I misread your post (my fault.)

Your English is just fine, by the way.

Boas tardes,

Ruben