PriorityQueue(Java)排序算法的麻烦:为什么排序与排序的ArrayList不同？
我当时在研究赫夫曼。但是我发现PriorityQueue的排序算法是有问题的；它没有进行足够的比较！然后，我编写了一个简单的类来测试集合的排序和PriorityQueue的排序：
public class Student implements Comparable<Student>{
String name;
int score;
int math;
public Student(int score, int math, String name) {
this.name = name;
this.score = score;
this.math = math;
}
public int compareTo(Student other) {
if (this.score > other.score) {
return -1;
} else if (this.score < other.score) {
return 1;
} else {
if (this.math > other.math) {
return -1;
} else {
return 1;
}
}
return 0;
}
public String toString() {
return("[" + name + " has Score: " + score + "(Math: " + math + ")]");
}
}但我得到的结果如下(在控制台上)：
Priority Queue::::::::::
[Jeremy Lin has Score: 2350(Math: 800)]
[Qian has Score: 2150(Math: 800)]
[PoorMath has Score: 2060(Math: 600)]
[Hui has Score: 1800(Math: 690)]
[Kaiyu has Score: 2060(Math: 800)]
[Chao has Score: 0(Math: 0)]
ArrayList sorted::::::::
[Jeremy Lin has Score: 2350(Math: 800)]
[Qian has Score: 2150(Math: 800)]
[Kaiyu has Score: 2060(Math: 800)]
[PoorMath has Score: 2060(Math: 600)]
[Hui has Score: 1800(Math: 690)]
[Chao has Score: 0(Math: 0)]怎么解释这个？太棒了！
非常感谢！
回答 2
Stack Overflow用户
发布于 2014-01-03 19:03:44
我想你可能对优先级队列的工作方式有一点误解.
PriorityQueue结构不能保证整个结构按任何特定的顺序排序。它只保证从顶部弹出的下一个元素将是最高优先级项。如果您查看PriorityQueue的API，它不允许随机访问PriorityQueue中的任何元素，它只允许访问下一个元素(非常像堆栈或队列结构)。
另一方面，ArrayList是一种允许随机访问的数据结构，所以在对其进行排序时，所有内部元素都是有序的。
因此，在您的示例中，结构都是正确的，因为它们都将Jeremy Lin显示为第一个条目。
如果您在PriorityQueue中做了类似的事情，您应该会看到与排序的ArrayList相同的顺序：
PriorityQueue<Student> pq;
//initialize PriorityQueue
while(pq.size() > 0)
{
System.out.println(pq.poll());
}我相信Java的PriorityQueue是基于标准的堆数据结构的。您可以在这里找到一些基本细节：结构)
Stack Overflow用户
发布于 2014-01-03 19:03:50
PriorityQueue不是一个排序的集合，它是一个有效地维护“最低”元素的集合。来自javadoc
对于指定的排序，此队列的头是最小的元素。如果多个元素被绑在最小的值上，那么头就是这些元素中的一个--领带是任意断的。队列检索操作轮询、删除、查看和元素访问队列顶部的元素。 方法iterator()中提供的Iterator不能保证以任何特定的顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用Arrays.sort(pq.toArray())。
https://stackoverflow.com/questions/20910696
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号