对象的比较（数据结构系列12）

目录

前言：

1.PriorityQueue

1.1PriorityQueue的特性

1.2PriorityQueue的构造器

1.3大根堆的创建

1.4PriorityQueue中函数的说明

2.java中对象的比较

2.1基本类型的比较

2.2对象的比较

2.2.1覆写基类的equals

2.2.2基于Comparable接口类的比较

2.2.3基于比较器比较

2.2.4三种方式对比

3.集合框架中PriorityQueue的比较方式

4.top—K问题

结束语：

---

前言：

1.PriorityQueue

1.1PriorityQueue的特性

我们先来简单的了解一下什么是PriorityQueue，然后再来了解java中的对象比较。

在java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，小编会在后续中给大家来介绍什么是线程安全什么是线程不安全的，我们现在先以PriorityQueue为例进行讲解。

我们先来看一下他是继承自哪些接口的。

我们可以看到他是继承自Queue这个接口的，所以我们以后在使用过程中可以直接使用Queue来定义一个优先级队列出来。 

如下所示：
 

import java.util.PriorityQueue;
import java.util.Queue;public class Test1 {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();//使用接口Queue<Integer> priorityQueue1 = new PriorityQueue<>();}
}

关于PriorityQueue的使用我们需要注意这几方面的问题。

1.使用时必须要导入PriorityQueue所在的包，如下所示：

import java.util.PriorityQueue;

2.PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。

如下所示：
 

package 优先级队列;import java.util.PriorityQueue;
class Student{public int age;public String name;public Student(int age, String name) {this.age = age;this.name = name;}
}
public class Test {public static void main(String[] args) {//下面的是可以的PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();priorityQueue.offer(1);priorityQueue.offer(2);//下面的是插入了两个类，两个类之间是不可以比较大小的PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>();priorityQueue2.offer(new Student(13,"张三"));priorityQueue2.offer(new Student(14,"张三"));}
}

3.不能插入null对象，否则就会抛出NullPointerException。

package 优先级队列;import java.util.PriorityQueue;public class Test1 {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();priorityQueue.offer(null);}
}

4.没有容量限制，可以插入任意多个元素，  其内部可以自动扩容。但是也不说真的就是没有任何容量限制，最大容量为堆的大小。

5.插入和删除元素的时间复杂度为O(log2N)。

6.PriorityQueue 底层使用了堆数据结构。

7.PriorityQueue默认情况下是小堆——即每次获取到的元素都是最小的元素。

如下所示：

import java.util.PriorityQueue;
import java.util.Queue;public class Test2 {public static void main(String[] args) {Queue<Integer> priorityQueue = new PriorityQueue<>();priorityQueue.offer(12);priorityQueue.offer(2);priorityQueue.offer(89);//底层是最小堆实现的System.out.println("堆顶元素是：" + priorityQueue.poll());//2}
}

结果如下所示：

1.2PriorityQueue的构造器

构造器	功能介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue（int initialCapacity）	创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则就会抛IIIegalArgumentException异常。
PriorityQueue（Collection<？extends E> c）	用一个集合来创建优先级队列。

PriorityQueue（Collection<？extends E> c）的实例如下所示：
代码如下所示：

import java.util.*;public class Test3 {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);Queue<Integer> priorityQueue = new PriorityQueue<>(list);//先构造list里面的在去构造自己的priorityQueue.offer(23);System.out.println("堆顶元素为：" + priorityQueue.poll());//1}
}

结果如下所示：

1.3大根堆的创建

我们在了解上述PriorityQueue的基本知识之后，我们知道它的底层是由小根堆构成的，那么我们如果是要构建一个大跟堆要怎么构建呢？

我们可以提供一个比较器，如下述代码所示：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;class IntCmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);//由于比较类型是Integer，也可以写作o2 - o1//如果是小根堆就是o1 - o2;}
}
public class Test4 {public static void main(String[] args) {//提供一个从大到小排序的比较器。IntCmp intCmp = new IntCmp();Queue<Integer> priorityQueue = new PriorityQueue<>(intCmp);priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(4);System.out.println("堆顶元素为：" + priorityQueue.poll());}
}

结果如下所示：

我们发现堆顶元素是最大的，这样我们就通过一个比较器来实现了大根堆的构建了。 

1.4PriorityQueue中函数的说明

函数名	功能介绍
boolean offer(E e)	插入元素e，插入成功后返回true，如果e对象为空，抛出空指针异常，当空间不够的时候会自动扩容
E peek()	获取优先级最高的元素，如果优先级队列为空，则返回null
E poll()	移除优先级队列最高的元素并返回，如果优先级队列为空，则返回null
int size()	获取有效元素的个数
void clear()	清空
boolean isEmpty()	检测优先级队列是否为空，空返回true

代码实例如下所示：

import java.util.PriorityQueue;
import java.util.Queue;public class Test5 {public static void main(String[] args) {Queue<Integer> priorityQueue = new PriorityQueue<>();//插入元素priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);priorityQueue.offer(4);priorityQueue.offer(5);priorityQueue.offer(6);//查看优先级队列的队首元素System.out.println("peek一次的队首元素为：" + priorityQueue.peek());//1System.out.println("peek两次的队首元素为：" + priorityQueue.peek());//1//弹出优先级队列的队首元素System.out.println("第一次弹出队首元素为：" + priorityQueue.poll());//1System.out.println("第二次弹出队首元素为：" + priorityQueue.poll());//2//优先级队列的有效元素个数System.out.println("队列中有效元素的个数为：" + priorityQueue.size());//4//判断是否为空System.out.println("clear之前队列是否为空：" + priorityQueue.isEmpty());//false//清空priorityQueue.clear();//判断是否为空System.out.println("clear之后队列是否为空：" + priorityQueue.isEmpty());//true}
}

结果如下所示：

 

2.java中对象的比较

2.1基本类型的比较

代码如下所示：

public class Test1 {public static void main(String[] args) {int a = 10;int b = 10;;System.out.println("a == b : " + (a == b));//trueSystem.out.println("a > b : " + (a > b));//falseSystem.out.println("a < b : " + (a < b));//falsechar c = 'A';char d = 'B';System.out.println("c == d : " + (c == d));//falseSystem.out.println("c > d : " + (c > d));//falseSystem.out.println("c < d : " + (c < d));//true}
}

结果如下所示：

2.2对象的比较

2.2.1覆写基类的equals

我们直接根据代码来说明问题。

代码如下所示：

class Student{public int age;public String name;public Student(int age, String name) {this.age = age;this.name = name;}
}
public class Test2 {public static void main(String[] args) {Student student1 = new Student(14,"张三");Student student2 = new Student(14,"张三");
//        System.out.println(student1 > student2);
//        System.out.println(student1 < student2);System.out.println(student1 == student2);//false}
}

结果如下所示：

在自定义对象中我们是不可以使用 > 和 < 来进行比较的，如下所示：

这里我们就有很多人好奇了，为什么==就可以比较而>和 < 就不可以比较了？我们在继续往下看。 

我们根据上述的代码可以看出来student1 和student2 用== 来进行比较是不相等的，但是在我们主观上认为student1和student2是同一个人的话那这个比较的结果就与我们预期的不符，那么为什么会出现这种情况呢？其实我们在进行对象之间的比较的时候我们是根据给每一个对象分配的地址来进行比较的，那么我们给他们分配的地址可定是不一样的，所以就会导致我们的比较结果出现问题，那么我们如果要比较两个地址空间内的内容是否一样我们该怎么进行比较呢？

我们之前也有过了解我们可以根据equals来进行比较，equals是专门用来比较两个地址空间内的内容是否一样的，一样则返回true，不同则返回false。

但是我们在使用之前得重写它的一些方法，否则还是会出现上述的问题，因为对于用户自定义实现的类型，都默认继承自Object类。在Object类中提供了equals方法，而==默认情况下调用的就是equals方法。

当我们重写了equals方法之后就可以进行比较了。快捷方法是在自定义类中使用Alt + Insert选择下面的这个方法一路回车就好了。

 

 

 

 

生成的equals方法，其中他是和hashCode是同时出现的，这个我们后面在给大家细说。

 

代码如下所示:

import java.util.Objects;class Student{public int age;public String name;public Student(int age, String name) {this.age = age;this.name = name;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Student student = (Student) o;return age == student.age && Objects.equals(name, student.name);}@Overridepublic int hashCode() {return Objects.hash(age, name);}
}
public class Test2 {public static void main(String[] args) {Student student1 = new Student(14,"张三");Student student2 = new Student(14,"张三");
//        System.out.println(student1 > student2);
//        System.out.println(student1 < student2);
//        System.out.println(student1 == student2);//falseSystem.out.println(student1.equals(student2));}
}

结果如下所示：
 

但是我们又会发现equals的一个缺点就是我们只能判断里面的值是否相同，但是不能判断谁大谁小，这样我们就引入了另一种比较方式，基于Comparable接口的比较。 

2.2.2基于Comparable接口类的比较

什么是Comparable接口呢? Comparable接口就是JDK提供的一种泛型的比类接口。具体的源码实现如下所示：

中间的红框内容我们可以直接理解为下面的这些：
返回值：

• <0：表示this指向的对象小于o指向的对象。
• ==0：表示this所指向的对象等于o指向的对象。
• >0：表示this所指向的对象大于o所指向的对象。 

对于我们上述代码中自己实现的自定义类Student来说要想用Comparable来进行比较的话我们就只需要实现Comparable接口即可，然后在类中重写CompareTo方法。

代码如下所示：

class Student1 implements Comparable<Student1>{public int age;public String name;public Student1(int age, String name) {this.age = age;this.name = name;}@Overridepublic int compareTo(Student1 o) {return o.age - this.age;}
}
public class Test3 {public static void main(String[] args) {Student1 student1 = new Student1(14,"李四");Student1 student12 = new Student1(14,"李四");System.out.println(student1.compareTo(student12));}
}

结果如下所示：

 

2.2.3基于比较器比较

我们如果是按照上述的Comparable接口进行比较的话我们就会把方法写死了，我们就只能按一个来进行比较，比如上述中的Student是按照age来进行排序的，按照比较器方式进行比较，具体步骤如下：

用户自定义比较器类，实现Comparator接口。

代码如下所示：

import java.util.Comparator;class Student2{public int age;public String name;public Student2(int age, String name) {this.age = age;this.name = name;}
}//按照年龄进行比较
class AgeInCmp implements Comparator<Student2> {@Overridepublic int compare(Student2 o1, Student2 o2) {return o1.age - o2.age;}
}
//按照姓名进行比较
class NameInCmp implements Comparator<Student2> {@Overridepublic int compare(Student2 o1, Student2 o2) {return o1.name.compareTo(o2.name);}
}public class Test4 {public static void main(String[] args) {Student2 student21 = new Student2(14,"李四");Student2 student22 = new Student2(14,"张四");AgeInCmp ageInCmp = new AgeInCmp();NameInCmp nameInCmp = new NameInCmp();System.out.println(ageInCmp.compare(student21,student22));System.out.println(nameInCmp.compare(student21,student22));}
}

结果如下所示：

 

2.2.4三种方式对比

覆写的方法	说明
Object.equals	因为所有类都是继承自Object的，所以直接覆写即可，不过只能比较相等与否
Comparable.compareTo	需要手动实现接口，侵入性比较，但一旦实现，每次用该类都有顺序，属于内部顺序，不够灵活。
Comparator.Compara	需要实现一个比较器对象，对待比较类的侵入性弱，但对于算法代码实现侵入性强

3.集合框架中PriorityQueue的比较方式

集合框架中的PriorityQueue底层使用结构，因此其内部的元素，必须要能够比较大小，PriorityQueue采用了Comparator和Comparable两种方式。

• Comparable是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparable接口，并覆写ComparaTo方法。
• 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法。

我们可以使用比较器创建大跟堆。

1.我们可以采用传比较器的方法来进行构建。

代码如下所示：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
class InCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}
}
public class Test6 {public static void main(String[] args) {//1.采用传送传感器来进行比较InCmp inCmp = new InCmp();Queue<Integer> priorityQueue = new PriorityQueue<>(inCmp);priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);System.out.println("堆的根结点是：" + priorityQueue.peek());}
}

结果如下所示：

2.我们也可以采用匿名内部类法。

代码如下所示：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;public class Test7 {public static void main(String[] args) {//2.匿名内部类法Queue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);System.out.println("堆的根结点是：" + priorityQueue.peek());}
}

结果如下所示：

3.lambda表达式法。

这个大家先做一个了解，后期小编会主要和大家讲解的。

代码如下所示：

import java.util.PriorityQueue;
import java.util.Queue;public class Test8 {public static void main(String[] args) {//3.lambda表达式Queue<Integer> priorityQueue = new PriorityQueue<>(((o1, o2) -> {return o2.compareTo(o1);}));priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);System.out.println("堆的根结点是：" + priorityQueue.peek());}
}

 

结果如下所示：

---

4.top—K问题

问题描述：即求数据集合中前k个最大的元素或者是最小元素，一般情况下数据量都比较大。

比如专业前十名，世界500强，富豪榜，游戏中前100的活跃玩家等。

我们就可以用优先级队列来解决这个问题了，我们将这些建成大跟堆来弹出前k个元素。

代码如下所示：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
class InCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}
}
public class Test1 {public static void find_Top_k(int[] array, int k) {int[] ret = new int[array.length];InCmp inCmp = new InCmp();Queue<Integer> maxHeap = new PriorityQueue<>(inCmp);for (int i = 0; i < array.length; i++) {maxHeap.offer(array[i]);}System.out.println("前" + k + "个是：");for (int i = 0; i < k; i++) {System.out.print(maxHeap.poll() + " ");}}public static void main(String[] args) {int[] array = {1,22,1,2,3,4,51,47,43,15,55,5,6,7,64};int k = 4;find_Top_k(array,k);}
}

结果如下所示：

 

---

结束语：

好啦这节小编就与大家分享到这里啦，里面有些可能大家还是有些看不懂，不重要大家可以先记着它，后期小编会一个一个给大家解释的，希望对大家有所帮助，想要学习的同学记得关注小编和小编一起学习吧！如果文章中有任何错误也欢迎各位大佬及时为小编指点迷津（在此小编先谢过各位大佬啦！）