Java集合与数据结构——优先级队列的使用及练习

淡淡的烟草味﹌ 2022-09-04 06:50 160阅读 0赞

### 文章目录 ###

*  一、对象比较的方法
 *   *  1.重写 compareTo 方法
     *  2.基于比较器的比较
 *  二、Java 优先级队列的 比较
 *   *  1.如何比较
     *  2.优先级队列解决 TOPK 问题
 *  三、练习
 *   *  1.查找和最小的 K 对数字
     *  2.最后一块石头的重量
 *  未完待续…

本文内容介绍大纲

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center]

接上篇 [Java集合与数据结构——优先级队列（堆）][Java]

# 一、对象比较的方法 #

上节课我们讲了优先级队列，优先级队列在插入元素时有个要求：

>  插入的元素不能是null或者元素之间必须要能够进行比较，为了简单起见，我们只是插入了Integer类型，那优先级队列中能否插入自定义类型对象呢？

我们先不用优先级队列来比较，先来看自定义类型如何进行比较…

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 1]

我们写了一个 Student 的一个类，类内部有姓名和年龄两个属性，我们直接通过数组类进行比较…

我们来看结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70]

那么我们一个自定义类型中有两个属性甚至多个属性的情况下，如何进行比较呢？

## 1.重写 compareTo 方法 ##

首先在 自定义类后面 实现 Comparable 接口，然后重写 compareTo 方法.

> 在定义类时，实现Comparble接口即可，然后在类中重写compareTo方法。

在这里 重写的compareTo 方法里 ，以年龄为基准进行排序

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 2]

现在我们再来运行

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 1]

这种比较方法有一个缺点：

>  需要手动实现接口，侵入性比较强，但一旦实现，每次用该类都有顺序，属于内部顺序. 我们只能通过 compareTo 里的规则进行排序.

## 2.基于比较器的比较 ##

> 1.用户自定义比较器类，实现Comparator接口

> 2.覆写Comparator中的compare方法

我们来写一个 年龄的比较器

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 3]

在数组排序时，我们可以将比较器作为参数，进行比较

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 4]

我们来看运行结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 2]

这种比较的方法我非常推荐，因为 对内部类不影响，我们只是建立了一个外部的比较器 ，当比较时 ，我们可以将比较器作为参数进行排序的.

# 二、Java 优先级队列的 比较 #

上节课我们学习了堆，这里我们就来看看 当自定义类的数据如何放入堆中.

## 1.如何比较 ##

集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了：

Comparble和Comparator两种方式。

> 1. Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法

> 2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 5]

我们可以在构造 PriorityQueue 时，直接将比较器 作为参数 比较.

我们来看结果：

![在这里插入图片描述][00bb4b0d8ddd482ea097337e25315052.png]

PriorityQueue 构造方法

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 3]

## 2.优先级队列解决 TOPK 问题 ##

我们要在下列数组中找到 最小的三个数据

> int \[ 8 \] arr = \{ 9,4,6,2,3,8,1,7 \} ;

建立一个 K=3 的 大堆，依次遍历，比堆顶元素 小的入队，堆顶元素出队.

> 建立一个 K=3 的大堆

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 6]

我们直接在 内部实现一个 comparator 的方法，o2 - o1是建立大堆，o1 - o2 是建立小堆.

TOPK 问题的思路我们在上一篇文章已经说的很清楚了，不明白的同学可以看一下 我的优先级队列的那一篇博客~~

完整代码展示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 7]

运行结果：

![在这里插入图片描述][c2f6e2e33eb146b882acfdc162ef3962.png]

运行成功，答案也正确了~~

# 三、练习 #

好了，之前铺垫了那么多，我们给大家来两道练习题：

## 1.查找和最小的 K 对数字 ##

leetcode 题目链接——[查找和最小的 K 对数字][K]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 4]

思路：

本题使用topk的经典解法。利用优先级队列PriorityQueue，构造大小为K的大根堆。

> 1、堆没有放满的情况下，直接往堆里面添加，直到添加到K的大小。

> 2、堆的大小等于K之后，每次存放数对的时候，和堆顶比较，如果堆顶的元素大于当前的数对，那么出队。然后添加当前数对。

> 3、直到遍历完两个数组。

注意点：

> 1、 遍历两个数组的时候，大小要和k取最小值。防止超出 时间限制，爆内存，给我们两个长度都很大的数组，要求取前10个最大的数，我们光是遍历完这两个数组都会超出时间限制，因为这两个数组是升序的，所以我们不必完全遍历，取 arr.length 与 K 的最小值同样能达到效果.

> 2、取结果的时候注意，一定要判断队列此时空不空，队列虽然大小是k，但是有可能放不满k个。

完整代码展示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 8]

运行结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 5]

## 2.最后一块石头的重量 ##

leetcode 题目链接——[最后一块石头的重量][Link 1]

题目描述  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 6]  
思路：

> 将所有石头的重量放入最大堆中。每次依次从队列中取出最重的两块石头 a 和b，必有 a ≥ b 。

> 如果 a > b，则将新石头a−b 放回到最大堆中；

> 如果a = b，两块石头完全被粉碎，因此不会产生新的石头。重复上述操作，直到剩下的石头少于 2 块。

> 最终可能剩下 1 块石头，该石头的重量即为最大堆中剩下的元素，返回该元素；也可能没有石头剩下，此时最大堆为空，返回 0。

代码展示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 9]

好了今天的知识就分享到这里，希望大家多多练习，熟练掌握，感谢大家的欣赏与关注！！

**谢谢欣赏！**

# 未完待续… #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/994f9fa6c3564702bd62ef84b5b71ac1.png
[Java]: https://blog.csdn.net/rain67/article/details/119277692
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220829/b5b5b5f81fa34e619a59950044cf1d1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70]: /images/20220829/3c7d14b410b747429c740f18706df21d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220829/fb2f0431735b4c68a48dfaad4668b0b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 1]: /images/20220829/166defa13307418885eac140839bd098.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20220829/c4aa7306d8844f05a97e8eba51ac4f88.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20220829/c50fb6b0d86142efab877c179c135b62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 2]: /images/20220829/49f92e1bafc340248736251fc62531a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20220829/f4eb54b369fa45c0ba015d49d222ece9.png
[00bb4b0d8ddd482ea097337e25315052.png]: /images/20220829/86460e836a5047b5a7edef2d1cce24b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 3]: /images/20220829/49a9bccf2acf4abf9d23fe62cc9a78ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20220829/d8badc8c6de74ccb84f38fb500b48f59.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20220829/ad10be7644444f6a8fdd25272c482d7c.png
[c2f6e2e33eb146b882acfdc162ef3962.png]: /images/20220829/7943a36d34444f08aab1b24eeb1c7d59.png
[K]: https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 4]: /images/20220829/411d0b1080034d4c94de6afc5472d97d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20220829/f8188cc77c69422da4d8b9c605df1479.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 5]: /images/20220829/5143044a7dd540f5a4617867b6320e91.png
[Link 1]: https://leetcode-cn.com/problems/last-stone-weight/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 6]: /images/20220829/793d800e50164e8c914ad628141a4336.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20220829/e911aec0e6444cb0ac9377e681259f19.png