CODEWITHSUNDEEP
javasortingcollectionspriority-queue
Leonardo Marques
Leonardo Marques

Reputation: 3951

PriorityQueue retrieve elements sorted

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?

Upvotes: 2

Views: 1238

Answers (3)

ddmps
ddmps

Reputation: 4390

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.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727037

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.

Upvotes: 3

Fred Foo
Fred Foo

Reputation: 363817

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.

Upvotes: 0

Related Questions