Java优先队列与自定义比较器

Question

我正在使用PriorityQueue和自定义的Comparator，但是结果并不总是令人满意。我应该按照平均分数、姓名、然后是学号排序。最终结果应该返回队列中剩余的按顺序排列的名字。剩下的名字都没问题，但是它们的顺序不正确。

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

- Kokufuu

---

{btsdaf} - David Lavender

{btsdaf} - Kokufuu

{btsdaf} - David Lavender

谢谢你，但在这个特定的任务中必须是double类型（它来自hackerrank.com）。 - Kokufuu

{btsdaf} - hoefling

{btsdaf} - Kokufuu

Answer 1

您的Comparator是正确的。问题在于您很可能是使用其Iterator来遍历列表。 PriorityQueue文档指出：

在方法iterator（）中提供的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());
}

或者在轮询时将它们添加到某种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());
        }
    }

}

学生（重命名，应该是单数形式）

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

- d.j.brown

Answer 2

从Java 8开始，您可以使用以下代码替换整个Comparator类：

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

如果您使用的是旧版本的Java，或坚持使用显式比较器，则必须对相等的值返回零。您还必须编写Comparator，以便与equals一致。来自文档：

如果比较器 c 在一组元素 S 上施加的排序与等于一致，则只有当对于 S 中的每个 e1 和 e2 时， c.compare（e1，e2）== 0 具有与 e1.equals（e2）相同的布尔值。使用能够强制实施与等号不一致的比较器来排序已排序的集合（或已排序的映射）时应该小心。假设使用具有显式比较器 c 的已排序集合（或已排序的映射）与从集合 S 中提取的元素（或键）。如果 c 在 S 上施加的排序与等于不一致，则排序后的集合（或排序后的映射）将表现出“奇怪”的行为。特别是，排序后的集合（或排序后的映射）将违反基于 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;
}

假设您的 Students 类具有匹配的 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;
}

- VGR