排除PriorityQueue(Java)算法的麻烦:为什么排序不同于排序的ArrayList？

Question

我正在研究霍夫曼.但我发现PriorityQueue的排序算法存在问题; 它没有足够的比较!然后我写了一个简单的类来测试Collections的排序和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)]

怎么解释这个？太奇怪了!

非常感谢!!

Answer 1

我想你可能会对优先级队列的工作方式产生轻微的误解......

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基于标准的Heap数据结构.你可以在这里找到一些基本的细节:http://en.wikipedia.org/wiki/Heap_(data_structure)