Java PriorityQueue with custom Comparator

Question

I am using a PriorityQueue and my own Comparator but somehow the end results are not always good. I should sort by grade average, than name, than id.no. At the end it should return the names left in the queue ordered. The remaining names are fine but their order is not. Input (name, grade avg, id.no):

add John 3,75 50
add Mark 3,8 24
add Shafaet 3,7 35
poll
poll
add Samiha 3,85 36
poll
add Ashley 3,9 42
add Maria 3,6 46
add Anik 3,95 49
add Dan 3,95 50
poll

Expected output:

Dan
Ashley
Shafaet
Maria

My result:

Dan
Ashley
Maria
Shafaet

Could you please help me to find the problem? Thank you in advance!

class StComp implements Comparator<Students> {
        @Override
        public int compare(Students st1, Students st2) {
            if (st1.getCgpa() == st2.getCgpa()) {
                if (st1.getName().equals(st2.getName()))
                    return st1.getId() - st2.getId();
                else
                    return st1.getName().compareTo(st2.getName());
            }
            else
                return (st1.getCgpa() < st2.getCgpa()) ? 1 : -1;
        }
    }

    StComp stComp = new StComp();
    PriorityQueue<Students> pq = new PriorityQueue<Students>(2, stComp);

Solution 1

Your Comparator is correct. The issue is that you're most likely traversing the list using its Iterator. The PriorityQueue documentation states:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

If you were to iterate over your PriorityQueue like this, you should see the correct results:

while (!pq.isEmpty())
    System.out.println(pq.poll().getName());
}

I've included an example at the end of this answer to fully demonstrate.

---

There are a couple of things you could do if you didn't want to clear your PriorityQueue. Personally I wouldn't recommend either approach as the initial choice of a PriorityQueue was not correct for the use-case, as they are not intended to be iterated over.

You could copy your PriorityQueue into an array, sort them using your Comparator implementation, iterate over the sorted array, e.g.:

Student[] students = pq.toArray(new Student[pq.size()]);
Arrays.sort(students, new StComp());
for (Student s : students) {
    System.out.println(s.getName() + " " + s.getCgpa() + " " + s.getId());
}

or add them to some sort of Collection whilst polling, then add them back to the PriorityQueue, e.g.:

Collection<Student> temp = new LinkedList<>();
while (!pq.isEmpty()) {
    Student s = pq.poll();
    System.out.println(s.getName() + " " + s.getCgpa() + " " + s.getId());
    temp.add(s);
}
pq.addAll(temp);

---

The example using your data to demonstrate:

Main

public class Main {

    public static void main(String[] args) {
        PriorityQueue<Student> pq = new PriorityQueue<>(new StComp());
        pq.add(new Student("John", 75, 50)); // Student name, grade average, id
        pq.add(new Student("Mark", 8, 24));
        pq.add(new Student("Shafaet", 7, 35));
        pq.poll();
        pq.poll();
        pq.add(new Student("Samiha", 85, 36));
        pq.poll();
        pq.add(new Student("Ashley", 9, 42));
        pq.add(new Student("Maria", 6, 46));
        pq.add(new Student("Anik", 95, 49));
        pq.add(new Student("Dan", 95, 50));
        pq.poll();

        // Not guaranteed to be in priorty order
        System.out.println("Using PriorityQueue's Iterator, may not be in the correct priority order.");
        for (Student s : pq) {
            System.out.println(s.getName() + " " + s.getCgpa() + " " + s.getId());
        }

        // Correct order, but removes from the Priority Queue
        System.out.println("\nIterating until empty using PriorityQueue.poll(), will be in the correct order.");
        while (!pq.isEmpty()) {
            Student s = pq.poll();
            System.out.println(s.getName() + " " + s.getCgpa() + " " + s.getId());
        }
    }

}

Student (renamed, should be singular)

public class Student {

    private double cgpa;
    private String name;
    private int id;

    public Student(String name, double cgpa, int id) {
        this.name = name;
        this.cgpa = cgpa;
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    public double getCgpa() {
        return cgpa;
    }

}

StComp (logic unchanged from question)

public class StComp implements Comparator<Student> {

    @Override
    public int compare(Student st1, Student st2) {
        if (st1.getCgpa() == st2.getCgpa()) {
            if (st1.getName().equals(st2.getName())) {
                return st1.getId() - st2.getId();
            } else {
                return st1.getName().compareTo(st2.getName());
            }
        } else {
            return (st1.getCgpa() < st2.getCgpa()) ? 1 : -1;
        }
    }
}

Output (for me at least, results may vary for the first Iterator variant)

Using PriorityQueue's Iterator, may not be in the correct priority order.
Dan 95.0 50
Ashley 9.0 42
Maria 6.0 46
Shafaet 7.0 35

Iterating until empty using PriorityQueue.poll(), will be in the correct order.
Dan 95.0 50
Ashley 9.0 42
Shafaet 7.0 35
Maria 6.0 46

Solution 2

As of Java 8, you can replace your entire Comparator class with this:

Comparator.comparingDouble(Students::getCgpa)
    .thenComparing(Students::getName)
    .thenComparingInt(Students::getId)

If you are using an older version of Java, or insist on keeping the explicit Comparator, you must return zero for equal values. You also must write your Comparator so it is consistent with equals. From the documentation:

The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.

Caution should be exercised when using a comparator capable of imposing an ordering inconsistent with equals to order a sorted set (or sorted map). Suppose a sorted set (or sorted map) with an explicit comparator c is used with elements (or keys) drawn from a set S. If the ordering imposed by c on S is inconsistent with equals, the sorted set (or sorted map) will behave "strangely." In particular the sorted set (or sorted map) will violate the general contract for set (or map), which is defined in terms of equals.

(In short, if two objects are equal, the Comparator must return zero when comparing them.)

@Override
public int compare(Students st1, Students st2) {
    int comparison = Double.compare(st1.getCgpa(), st2.getCgpa());
    if (comparison == 0) {
        comparison = st1.getName().compareTo(st2.getName());
    }
    if (comparison == 0) {
        comparison = st1.getId() - st2.getId();
    }
    return comparison;
}

This assumes that your Students class has a matching equals method:

@Override
public boolean equals(Object obj) {
    if (obj instanceof Students) {
        Students other = (Students) obj;
        return Double.compare(this.getCga(), other.getCga()) == 0
            && this.getName().equals(other.getName())
            && this.getId() == other.getId();
    }
    return false;
}