当前位置： 首页 > article >正文

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

article 2024/11/18 1:26:11

目录

前言：

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>{

    @Override
    public 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());//1
        System.out.println("peek两次的队首元素为：" + priorityQueue.peek());//1
        //弹出优先级队列的队首元素
        System.out.println("第一次弹出队首元素为：" + priorityQueue.poll());//1
        System.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));//true
        System.out.println("a > b : " + (a > b));//false
        System.out.println("a < b : " + (a < b));//false

        char c = 'A';
        char d = 'B';
        System.out.println("c == d : " + (c == d));//false
        System.out.println("c > d : " + (c > d));//false
        System.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;
    }

    @Override
    public 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);
    }

    @Override
    public 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);//false
        System.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;
    }

    @Override
    public 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> {

    @Override
    public int compare(Student2 o1, Student2 o2) {
        return o1.age - o2.age;
    }
}
//按照姓名进行比较
class NameInCmp implements Comparator<Student2> {

    @Override
    public 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> {

    @Override
    public 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>() {
                    @Override
                    public 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> {

    @Override
    public 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);
    }
}


结果如下所示：

 


结束语：

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


http://www.kler.cn/a/7406.html

相关文章：

  • 【Android、IOS、Flutter、鸿蒙、ReactNative 】启动页
  • transformers 操作篇
  • Spark RDD sortBy算子什么情况会触发shuffle
  • reduce-scatter：适合分布式计算；Reduce、LayerNorm和Broadcast算子的执行顺序对计算结果的影响，以及它们对资源消耗的影响
  • Android 中的 Zygote 和 Copy-on-Write 机制详解
  • 智能化护士排班系统的设计与实现（文末附源码）
  • 2023中国程序员薪酬报告出炉，你拖后腿了吗？
  • ViewBinding用法
  • mysql知识点看这一篇就够了！
  • 振动监测信号的角度域之阶次分析（1）
  • ChatGPT 存在很大的隐私问题
  • Java分布式事务（七）
  • 前端后端交互系列之原生Ajax的使用
  • C的实用笔记39——结构体占用内存大小(了解)
  • linux信号量及其实例
  • Vue+H5如何适配各个移动端？
  • netty 实现websocket 携带参数建立连接
  • VSCode卸载、重装配置、常用快捷键
  • 【ChatGPT 】国内无需注册 openai 即可访问 ChatGPT：ChatGPT Sidebar 浏览器扩展程序的安装与使用
  • 【软件设计师10】软件工程
  • SpringSecurity实战解析
  • 为什么系统的Swap变高了?
  • 吴恩达机器学习--逻辑回归
  • 分布式id生成方案及springboot进行集成
  • JavaSE基础(26) 接口
  • 面向对象编程（基础）5：类的成员之二：方法(method)