带有自定义比较器的Java优先级队列

Question

我使用的是PriorityQueue和我自己的比较器，但最终结果并不总是好的。我应该按平均成绩、姓名、身份证进行排序。最后，它应该返回队列中剩余的名称。其余的名字都很好，但顺序不同。输入（名称、平均等级、识别号）：

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

从Java8开始，您可以用以下内容替换整个比较器类：

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

如果您使用的是旧版本的Java，或者坚持保留显式比较器，那么必须返回零表示相等的值。您还必须编写比较器，使其与equals一致。从文件中：

当且仅当c.compare（e1， e2）==0具有与S相同的布尔值时，比较器c对一组元素S施加的排序被认为与等于一致e1.equals（e2）用于S中的每个e1和e2。

当使用比较器时，应谨慎使用，比较器能够对排序集（或排序映射）施加与等于不一致的排序。假设带有显式比较器c的排序集（或排序映射）与从集合S中绘制的元素（或键）一起使用。如果c对S施加的顺序与equals不一致，则排序集（或排序映射）的行为将“异常”特别是，排序集（或排序映射）将违反集合（或映射）的一般契约，该契约是根据equals定义的。

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

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

这假设您的学生班级有一个匹配的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

您的比较器是正确的。问题是，您很可能正在使用其迭代器来遍历列表。PriorityQueue文档说明：

方法Iterator（）中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素。

如果您要像这样迭代您的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());
}

或者在轮询时将它们添加到某种集合中，然后将它们添加回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());
        }
    }

}

学生（重命名，应为单数）

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

输出（至少对我来说，第一个迭代器的结果可能不同）

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