Java 带有自定义比较器的 PriorityQueue

Question

我正在使用 PriorityQueue 和我自己的比较器，但不知何故最终结果并不总是好的。我应该按平均成绩排序，而不是按姓名排序，而不是 id.no。最后它应该 return 队列中剩下的名字排序。其余的名字很好，但它们的顺序不是。输入（姓名，平均成绩，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

预期输出：

Dan
Ashley
Shafaet
Maria

我的结果：

Dan
Ashley
Maria
Shafaet

你能帮我找出问题所在吗？提前致谢！

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);

Answer 1

从 Java 8 开始，您可以将整个比较器 class 替换为：

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

如果您使用的是 Java 的旧版本，或者坚持保留显式比较器，则必须 return 零才能获得相等的值。您还必须编写比较器，使其 与等号一致。 来自 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.

（简而言之，如果两个对象相等，比较器在比较它们时必须return为零。）

@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;
}

假设您的学生 class 有匹配的 equals 方法：

@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;
}

Answer 2

您的 Comparator 是正确的。问题是您很可能使用 Iterator 遍历列表。 PriorityQueue documentation 状态：

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

如果您要像这样迭代 PriorityQueue，您应该会看到正确的结果：

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

我在这个答案的末尾包含了一个例子来充分展示。

如果您不想清除 PriorityQueue，可以采取一些措施。就我个人而言，我不推荐任何一种方法，因为 PriorityQueue 的初始选择对于用例来说是不正确的，因为它们不打算被迭代。

您可以将 PriorityQueue 复制到一个数组中，使用 Comparator 实现对它们进行排序，遍历排序后的数组，例如：

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());
}

或在轮询时将它们添加到某种 Collection，然后将它们添加回 PriorityQueue，例如：

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);

使用您的数据演示的示例：

主要

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（重命名，应为单数）

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（问题逻辑不变）

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;
        }
    }
}

输出（至少对我来说，第一个 Iterator 变体的结果可能会有所不同）

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

Java 带有自定义比较器的 PriorityQueue

Java PriorityQueue with custom Comparator

java

priority-queue