关于使用compareTo方法实现优先级高低的问题

Question

老师好，compareTo那里定义优先级高低的时候，实在有点搞不懂。当优先级队列queue底层是用最大堆实现的时候，频次小的优先级高这个我能理解，就是二叉堆的父节点比左右子节点都要小；可为什么换成jdk底层最小堆实现的队列的时候，频次大的优先级又最高了，那二叉堆的父节点不是要比左右子节点的数值都要高了？那从map里筛选高频的时候，map.get(key)>pq.getFront().freq 的判断就又问题了啊，因为pq.getFront().freq取出来就是最大的频次了啊，有点晕，不知道是自己对compareTo的理解有问题，还是对优先级队列的添加元素的理解有问题，还请老师指点迷津~

Answer 1

liuyubobobo 2019-08-05 02:25:45

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

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

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

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

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

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

  1
 / \
2   3

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

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

继续加油！：）

• 提问者 ybb_bzZ0sdf #1

  bobo老师，请看一下这个问题下的我的回答，这样理解是对的吗？

• 提问者 ybb_bzZ0sdf #2

  非常感谢！

Answer 2

提问者 ybb_bzZ0sdf 2019-08-05 12:11:08

那可能是我对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~

• liuyubobobo #1

  非常正确。你的这个例子，把这些Student放进最小堆，最小堆顶是30。就是你说的，语义改变了。大小关系不是一成不变的，是被定义出来的，这就是compareTo的意义。再理解一下我说的这句话：我们可以说 1 比 2 小，2 比 3 小（1个萝卜比2个萝卜少；2个萝卜比3个萝卜少）；也可以说 1 比 2 大，2 比 3 大（比如第一名比第二名厉害，第二名比第三名厉害）。

• 提问者 ybb_bzZ0sdf 回复 liuyubobobo #2

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