PriorityQueue retrieve elements sorted

Question

I'd like to have a sorted collection in java that I can iterate over it. From what I read a PriorityQueue is the thing that I need but hen I can't figure out how to retrieve the elements ins a sorted manner...

I did this test example:

Main.java

import java.util.PriorityQueue;
public class Main {

public static void main(String[] args) {
    PriorityQueue<Object> queue=new PriorityQueue<Object>();
    Object o1=new Class1("o1");
    Object o2=new Class2("o2");
    Object o3=new Class1("o3");
    Object o4=new Class1("o4");
    Object o5=new Class2("o5");
    Object o6=new Class2("o6");
    Object o7=new Class1("o7");
    Object o8=new Class2("o8");
    Object o9=new Class1("o9");
    Object o0=new Class1("o0");
    queue.add(o7);
    queue.add(o4);
    queue.add(o3);
    queue.add(o8);
    queue.add(o5);
    queue.add(o1);
    queue.add(o2);
    queue.add(o9);
    queue.add(o0);
    queue.add(o6);

    for (Object object : queue) {
            System.out.println(object);
    }
}
}

Class1.java:

public class Class1 implements Comparable<Object>{
String name;

public Class1(String name) {
    super();
    this.name = name;
}

@Override
public String toString() {
    return "Class1 [name=" + name + "]";
}

@Override
public int compareTo(Object o) {
    return (o instanceof Class1)?compareTo((Class1)o):compareTo((Class2)o);
}

public int compareTo(Class1 o){
    return name.compareTo(o.name);
}

public int compareTo(Class2 o){
    return name.compareTo(o.name2);
}

}

Class2.java:

public class Class2 implements Comparable<Object>{
String name2;

public Class2(String name) {
    super();
    this.name2 = name;
}

@Override
public String toString() {
    return "Class2 [name=" + name2 + "]";
}

@Override
public int compareTo(Object o) {
    return (o instanceof Class1)?compareTo((Class1)o):compareTo((Class2)o);
}

public int compareTo(Class1 o){
    return name2.compareTo(o.name);
}

public int compareTo(Class2 o){
    return name2.compareTo(o.name2);
}

}

This returns:

Class1 [name=o0]
Class1 [name=o1]
Class2 [name=o2]
Class2 [name=o5]
Class2 [name=o6]
Class1 [name=o4]
Class1 [name=o3]
Class1 [name=o9]
Class2 [name=o8]
Class1 [name=o7]

What do I need to do to iterate in a sorted fashion over this collection?

While HeapSort which is pretty much what converting an array to a PriorityQueue is supposed to be O(nlogn) you should consider a TreeSet instead of you just want a sorted collection. — Benjamin Gruenbaum, May 24 '13 at 10:18

score 2 · Accepted Answer · answered May 24 '13 at 10:25

2

The elements are returned to you in the sorted order only on dequeueing them. When you iterate the queue without dequeueing, the order is internal to the implementation of the priority queue.

Replacing the loop with the code below gives you the data in the correct order:

Object last;
while ((last = queue.poll()) != null) {
        System.out.println(last);
}

Since dequeueing is guaranteed to happen in the correct order, this produces the following output:

Class1 [name=o0]
Class1 [name=o1]
Class2 [name=o2]
Class1 [name=o3]
Class1 [name=o4]
Class2 [name=o5]
Class2 [name=o6]
Class1 [name=o7]
Class2 [name=o8]
Class1 [name=o9]

Here is a demo on ideone.

answered May 24 '13 at 10:25

Sergey Kalinichenko

714,442
84
1,110
1,523

1

Although I would be satisfied with using any other Collection type this seems to be the method that most directly answers my question. Thank you. – Leonardo Marques May 24 '13 at 10:47
I like the structure of your while statement. Don't you think this is more readable: while (queue.peek() != null) { System.out.println(queue.poll()); } – GilbertS Apr 04 '20 at 16:28
1

@GilbertS Assignment inside the "while" saves me a second walk through the queue. Your version is undoubtedly more readable, though. – Sergey Kalinichenko Apr 04 '20 at 18:27

score 1 · Answer 2 · answered May 24 '13 at 10:32

A PriorityQueue does not guarantee any ordering of it's elements when traversing through the iterator. It only guarantees that the first element is the "smallest" one. As it is a Queue, it is supposed to be used as a temporary collection that you poll from.

Instead, as @BenjaminGruenbaum commented you can use a TreeSet which guarantees that the iterator will return the elements order.

Another option is to use Collections.sort() to sort any List when you need it to be sorted.

P.S. It looks like you could use some inheritance with Class1 and Class2 as it could simplify a lot of your code - you would only need the toString() methods as they're the only ones that are different.

Regarding the P.S. I thought about that but since the field being compared is not common to both classes I didn't do it. In the other hand the new Parent class could have an abstract method called toCompare that would return the right field. Anyway it is just an example that mimics my real problem. Thank you. — Leonardo Marques, May 24 '13 at 10:42

score 0 · Answer 3 · answered May 24 '13 at 10:22

0

A priority queue isn't really a sorted container; it's more like a stack or queue that pops off elements in sorted order. You'll want to use a container that implements SortedSet.

answered May 24 '13 at 10:22

Fred Foo

355,277
75
744
836

"pops off elements in sorted order." that is the thing... there is no way to pop it in a sorted order that I can find... – Leonardo Marques May 24 '13 at 10:38

PriorityQueue retrieve elements sorted

3 Answers3