带有自定义Comparator的Java PriorityQueue

Question

我正在使用PriorityQueue和我自己的比较器,但不知何故最终结果并不总是好的.我应按等级平均值而不是名字排序,而不是id.no. 最后它应该返回队列中留下的名字.其余的名字很好,但他们的顺序不是.输入(名称,等级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

预期产量:

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

你Comparator是对的.问题是你最有可能使用它来遍历列表Iterator.该PriorityQueue文件 规定:

方法iterator()中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素.

如果您要PriorityQueue像这样迭代,您应该看到正确的结果:

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

我在这个答案的最后给出了一个例子来充分展示.

如果你不想清除你的话,你可以做几件事PriorityQueue.就个人而言,我不推荐任何一种方法,因为a的初始选择对于用例来说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