📕 PriorityQueue(优先级队列)自定义类型对象的比较
在前面一遍文章中,我们了解到了什么是堆,为了简单理解起见我们采用了基本数据类型(Integer)去进行比较,下面我们通过代码来分析是如何实现自定义的类型进行比较。
我们首先定义一个学生类:
public class Student { public int ID; public String name; public Student(int Id,String name){ this.ID = Id;//学号 this.name=name;//姓名 } } class priority{ public static void main(String[] args) { PriorityQueue<Student> priorityQueue = new PriorityQueue<>(); priorityQueue.offer(new Student(1,"1号")); priorityQueue.offer(new Student(2,"2号")); } }
比较的结果:
之前我们了解到,优先级队列的底层其实就是一个堆,我们为了满足堆的性质,我们必须进行元素的比较,而我们自定义类型是无法直接比较的,需要我们通过指定的方法进行比较的。那么我们只有通过以下几种方式进行自定义类型的比较!
📘 Comparable接口进行比较
📖 实现Comparable接口
我们首先必须先要在自定义类型中让它实现Comparable接口,重写comparable方法
public class Student implements Comparable<Student>{ public int ID; public String name; public Student(int Id,String name){ this.ID = Id;//学号 this.name=name;//姓名 } @Override public int compareTo(Student o) { return this.ID-o.ID; } @Override public String toString() { return "Student{" + "ID=" + ID + ", name='" + name + '\'' + '}'; } } class priority{ public static void main(String[] args) { PriorityQueue<Student> priorityQueue = new PriorityQueue<>(); Student student1 = new Student(1,"1号"); Student student2 = new Student(2,"2号"); priorityQueue.offer(student1); priorityQueue.offer(student2); System.out.println(priorityQueue); } }
运行结果:
📖源码分析
从以上的结果我们可以看出,这时候我们自定义的student1和student2两个对象可以进行比较,下面我们通过源码来分析以下是如何比较的:
首先,添加一个元素,源码中的E表示的是泛型,这个之后我们会详细讲解,第一次传过来的是student1,student1肯定不等于null,(modCount++无关我们分析),然后源码中size=0;所以i是为0的,下一步判断是否超过数组长度(因为优先级队列底层就是一个数组)
如果超过了长度,原容量如果小于64,那么就会使2*oldcapacity+2扩容,否则就是1.5倍的扩容
然后此时size=1,由于i是为0的,那么就直接把student1直接放到queue[0]的位置
此时在加入student2,那么以上的执行步骤是一样的,只不过student2放进来的时候i是不等于0的,所以只能执行else语句,else语句之后就会来到下列方法,而一开始的时候就将comparator置为null,所以只能执行else语句。
来到else语句之后将进行以下操作,先将student2强转为可比较的类型,此时k是由i传参过来的,那么k为1,e取出queue[0]中的值,也就是student1,符合if语句中的比较方式(也就是利用重写comparable中student2中的学号减去student1中的学号差值),那么此时将会直接跳出循环,不进行交换,所以queue[1]=student2的值
📙 Comparator比较器进行比较
📖 构造Comparator比较器
class ID implements Comparator<Student>{ @Override public int compare(Student o1, Student o2) { return o1.ID-o2.ID; } } class priority{ public static void main(String[] args) { ID id = new ID(); PriorityQueue<Student> priorityQueue = new PriorityQueue<>(id); Student student1 = new Student(1,"1号"); Student student2 = new Student(2,"2号"); priorityQueue.offer(student1); priorityQueue.offer(student2); System.out.println(priorityQueue); } }
注意这里在利用Comparator构造时,是需要添加比较器的引用的,否则Comparator默认为null,这样的话是不能利用Comparator进行比较。
📖 源码分析
经过对Comparatable源码分析,其实Comparator的分析也是差不多的,就是在shifUp上要走的就是if语句了
过来之后,在调用方法比较,比较的方法其实是与Comparatable是一样的
📖 匿名内部类的方式
这里并不是将Comparator这个接口实例化,而是写成了一个匿名内部类的形式,至于具体什么是内部类,在之后的文章中我们将会解说。
运行结果:
在之后,其实这里的这个内部类可以转化为lamada表达式,代码会变的更简洁,但是代码的可阅读性就会变的更差。
📒 覆写基类中的equals
public class Student { public int ID; public String name; public Student(int Id,String name){ this.ID = Id;//学号 this.name=name;//姓名 } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return ID == student.ID && Objects.equals(name, student.name); } @Override public int hashCode() { return Objects.hash(ID, name); } @Override public String toString() { return "Student{" + "ID=" + ID + ", name='" + name + '\'' + '}'; } } class priority{ public static void main(String[] args) { Student student1 = new Student(1,"1号"); Student student2 = new Student(1,"1号"); System.out.println(student1.equals(student2)); } }
📖注意事项:
如果指向同一个对象,返回 true
如果传入的为 null,返回 false
如果传入的对象类型不是 Student,返回 false
按照类的实现目标完成比较,例如这里只要学号和姓名一样,就认为是相同的牌
注意下调用其他引用类型的比较也需要 equals,例如这里的 name 的比较
📖缺陷:
只能按照相等与否进行比较,不能按照大于或小于的方式进行比较
🔓 总结
1 利用JAVA源码去分析,可以发现,对于非基本数据类型的对象的比较就是需要我们通过设定对应的比较方式去进行比较,这样我们才可以进行比较
2 优先级队列中是不能offer(null)的,这样会抛出空异常!
3 对于Comparable接口,正如我们之前所学的那样,拥有一个比较大的缺点,就是对类的侵入性强,如果我们改动类里面的比较方式,那么就可能会导致代码出现异常。
4 对于Comparable,我们其实可以使用比较器Comparator去实现,从而可以减少对类的侵入性。
5 对于Comparator比较器而言,我们可以写多个比较器,可以利用学号写一个比较器,也可以利用姓名写一个比较器。