2回答

liuyubobobo

2019-08-05

已采纳

我觉得在这里，你可能混淆了“优先级”和“大小关系”的概念。

在这个问题中，我们创建的优先队列，要先拿出频次小的元素。所以，不管是用最大堆实现，还是用最小堆实现，都是“频次小的优先级”。

但关键是，什么叫优先级？怎么定义大小关系。

如果底层实现是最大堆，堆顶却是那个最小的元素。说明，在这个堆中，元素之间的排序方式是：元素值越小，这个元素越大，所以最小元素在最大堆的堆顶。

但如果底层实现是最小堆，堆顶还那个最小的元素。说明，在这个堆中，元素之间的排序方式是：元素值越小，这个元素越小，所以最小元素在最小堆的堆顶。

所以，在这两种堆中，其实，元素的排列方式是一样的。但由于我们的堆，一个是最大堆，一个是最小堆。所以，面对同样的这个结构：

  1
 / \
2   3

最大堆说的是：1比2和3都要大；最小堆说的是1比2和3都要小。那么显然，他们定义大小关系的方式，是不一样的。

所以说，大和小是相对的。比如，1，2，3这三个数字，我们可以说 1 比 2 小，2 比 3 小（1个萝卜比2个萝卜少；2个萝卜比3个萝卜少）；也可以说 1 比 2 大，2 比 3 大（比如第一名比第二名厉害，第二名比第三名厉害）。

继续加油！：）

1

2

ybb_bzZ0sdf

非常感谢！

2019-08-05

共2条回复

ybb_bzZ0sdf

提问者

2019-08-05

那可能是我对compareTo的理解有问题，我做了个测试，声明一个Student类（成员变量id,name）实现Comparable接口，然后重写compareTo()方法，

public int compareTo(Student o) {
    if(this.id < o.id)
        return 1;
    else if(this.id > o.id)
        return -1;
    else
        return 0;
}

最后如下做一个打印测试（toString方法省略），

List<Student> studentList = new ArrayList<>();
Student s1 = new Student(10,"s1");
Student s2 = new Student(20,"s2");
Student s3 = new Student(30,"s3");
studentList.add(s1);
studentList.add(s2);
studentList.add(s3);

Collections.sort(studentList);

System.out.println(studentList);

结果如下：

[Student:{id=30, name=s3}, Student:{id=20, name=s2}, Student:{id=10, name=s1}]

从数值上看，是降序排列，但是不是放到优先队列这个案例中，也可以理解为是升序，只不过是数值大小的语意改变了，变成了id=30 < id=20 < id=10 的顺序，10反而要看做是最大值。

所以最大堆的堆顶反而是10。

可以这样理解吗？bobo老师。真实绕晕ing~

0

2

ybb_bzZ0sdf

回复

liuyubobobo

晕了一个晚上，经过bobo老师指点后，思维模式终于强行扭过来。一脸泪~网上各种博客都没有对compareTo的释义有个很好的解释，也是醉了，多谢老师~

2019-08-05

共2条回复