java - PriorityQueue(Java) : Why is ordering different than a sorted ArrayList? 的排序算法出现问题

标签 java algorithm sorting arraylist priority-queue

<分区>

我正在研究霍夫曼。但是我发现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)]

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

非常感谢!

最佳答案

我想你可能对优先级队列的工作原理有点误解......

PriorityQueue 结构不保证整个结构按任何特定顺序排序。它只保证您从其顶部弹出的下一个元素将是最高优先级的项目。如果您查看 PriorityQueue 的 API，它不允许随机访问 PriorityQueue 中的任何元素，它只允许访问下一个元素(很像 Stack 或 Queue 结构)。

另一方面，ArrayList 是一种允许随机访问的数据结构，因此当您对其进行排序时，所有内部元素都是有序的。

因此在您的示例中，结构都是正确的，因为它们都将 Jeremy Lin 显示为第一个条目。

如果您对 PriorityQueue 执行了类似的操作，您应该会看到与已排序的 ArrayList 相同的顺序:

PriorityQueue<Student> pq;

//initialize PriorityQueue

while(pq.size() > 0)
{
   System.out.println(pq.poll());
}

我相信 Java 的 PriorityQueue 是基于标准堆数据结构的。您可以在此处找到一些基本详细信息:http://en.wikipedia.org/wiki/Heap_(data_structure)

关于java - PriorityQueue(Java) : Why is ordering different than a sorted ArrayList? 的排序算法出现问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20910696/

上一篇：arrays - 降低 Perl 数组的时间复杂度

下一篇：algorithm - 如何用链表实现一个不相交集的数据结构？

C++ vector 的所有组合

bash - 删除所有出现的重复行

java - 如何使用数组中的字段对ElasticSearch索引进行排序？

java - 多 react 器设计 - 我是否试图重新发明 Netty？

java - 为什么转换为通用子类型会产生警告？

php拼写检查迭代优化

python - 使用 np.sort 排序但结果不正确

java - 如何读取CtMethod的数据

java - java spring 如何使一个对象在所有包中可用