Java-数据结构-优先级队列(堆)-(二) (゚▽゚*)

news/2024/9/24 20:14:53/

文本目录:

❄️一、PriorityQueue的常用接口:

          ➷ 1、PriorityQueue的特性:

          ➷ 2、使用PriorityQueue的注意:

           ➷ 3、PriorityQueue的构造:

    ☞  1、无参数的构造方法:

     ☞  2、有参数的构造方法:

     ☞  3、带一个参数comparator的构造方法:

     ☞  4、用集合的构造方法:

           ➷ 4、PriorityQueue的插入和删除等方法:

    ☞  1、插入方法(offer(E e)):

    ☞  2、删除方法( poll() ) 和 查看优先级最高的( peek() ):

     ☞  3、获得有效元素的个数( size() ):

     ☞  4、判空( isEmpty() ):

 ❄️二、堆的应用:

          ➷ 1、PriorityQueue的实现:

          ➷ 2、堆排序:

          ➷ 3、Top-k问题:

  ❄️总结:


❄️一、PriorityQueue的常用接口:

          ➷ 1、PriorityQueue的特性:

        在 Java 集合中给我们提供了两种优先级队列:PriorityQueuePriorityBlockingQueue,它们肯定是有区别的,我们的 PriorityQueue  线程不安全PriorityBlockingQueue 线程安全的 ,我们这次呢主要介绍 PriorityQueue 

         我们还是请出我们的老朋友:

我们可以看到我们的  PriorityQueue  是实现 Queue 这个接口的。


          2、使用PriorityQueue的注意:

在我们使用  PriorityQueue  的时候我们要注意:


1、在我们使用  PriorityQueue  的时候我们需要导入包:

所以我们一定要导包。


 2、 PriorityQueue  中存放的数据必须是可以比较大小的,不能插入无法比较大小的对象,否则          会抛出 ClassCastException 异常。

     因为我们的优先级队列需要比较对象之后才进行存入,这时候我们比较时候要强转成 Comparable 这个,我们来看看这个的底层代码:

所以我们必须要存入可以比较的对象。 


3、我们不能插入 null 对象,否则会抛出 NullPointerException 这个异常。我们来看:

存入 null 就会抛出异常。 


4、没有容量限制,可以插入任意多个元素,其内部可以自动扩容。


5、插入和删除元素的时候的时间复杂度为O(logN)


6、 PriorityQueue 底层使用了堆的数据结构


7、 PriorityQueue 默认情况下是 小堆 ------ 就是每次获得堆里最小的元素


           3、PriorityQueue的构造:

     我们的 优先级队列 的构造方法常见的有几种构造方法,我们来一一介绍来看,但是呢在我们介绍构造方法之前呢,我们来看看 优先级队列 的底层代码的一些代码:


    ☞  1无参数的构造方法:

我们来看看这个无参构造的底层代码:

java">public PriorityQueue(int initialCapacity) {this(initialCapacity, null);}

 这里呢我们调用的两个参数的构造方法,我们的 容量是默认的 11 个容量。


     ☞  2有参数的构造方法:

   我们同样先来看看底层的代码:

java">public PriorityQueue(int initialCapacity) {this(initialCapacity, null);}

这个呢就是创建一个 容量 为 initialCapacity 这个容量的 优先级队列

这里调用的同样是两个参数的构造方法。

这里要注意我们传入的参数不能 < 1。


     ☞  3带一个参数comparator的构造方法:

java">public PriorityQueue(Comparator<? super E> comparator) {this(DEFAULT_INITIAL_CAPACITY, comparator);}

这里同样是调用带两个参数的构造方法,我们传入的是一个比较器。容量 还是 11 这个默认参数


接下来我们来看看对于这几个构造方法所调用的 两个参数的构造方法是什么样的:

java">public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {if (initialCapacity < 1)throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator;}

这个就是我们的底层代码。 

这里我们会直接把传入的参数直接给到 queue 这个的容量。之后把第二个参数给到我们的比较器 


     ☞  4用集合的构造方法:

我们还是先来看看底层代码:

java">public PriorityQueue(Collection<? extends E> c) {if (c instanceof SortedSet<?>) {SortedSet<? extends E> ss = (SortedSet<? extends E>) c;this.comparator = (Comparator<? super E>) ss.comparator();initElementsFromCollection(ss);}else if (c instanceof PriorityQueue<?>) {PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;this.comparator = (Comparator<? super E>) pq.comparator();initFromPriorityQueue(pq);}else {this.comparator = null;initFromCollection(c);}}

这里就是我们传入的集合会直接给到我们的数组中,来构造。 


           4、PriorityQueue的插入和删除等方法:

    这里呢我们只介绍一下关于插入方法的操作的流程,其余的呢,我们看一下演示结构,因为和我们上次博客实现的堆的方法原理是一样的。


    ☞  1、插入方法(offer(E e)):

     我们在上一个博客中已经介绍了堆的插入是如何实现的了,这里呢是类似的,我们在这里呢,我们直接来看看这个方法在Java中的执行流程图:  

    这里的 compareTo 这个方法默认的是 this.val - o.val 在上面就是 15 - 11,这样得到的就是小根堆如果我们想要实现大根堆,就把其变成 o.val - this.val 就可以了,我们来看看如何实现的: 


    ☞  2、删除方法( poll() ) 和 查看优先级最高的( peek() ):

我们来看看删除优先级最高的栈顶数据:


     ☞  3、获得有效元素的个数( size() )


     ☞  4、判空( isEmpty() )


 ❄️二、堆的应用:

          ➷ 1、PriorityQueue的实现:

     我们的 PriorityQueue 的底层使用的就是堆来实现的。


          ➷ 2、堆排序:

     堆排序就是使用堆的思想来实现排序,我们的排序有两种排序,升序 和 降序,我们分为来那个步骤来进行堆排序:

    1、建堆:

升序:建大堆。

降序:建小堆。

    2、利用堆删除的思想来进行排序:

      我们来使用堆排序 创建升序 来进行介绍如何建成堆排序。

      就是把一个 大根堆 的 第一个数据和最后一个数据进行交换,之后我们把交换完的第一个数据向下调整,再次变成大根堆但是要注意,我们交换完之后的位置不用再调整,我们这时候要使用 一个 临时变量进行记录 我们 向下调整 的判断是否结束的位置。我们来看看流程图:

这个理解之后呢,我们来看看这个对于 使用大根堆来实现升序 的代码要如何实现: 

java"> private void shiftDown(int parent,int usedSize) {int child = parent * 2 + 1;//parent根节点的左子树的节点while (child < usedSize) {//判断有没有右子树,如果有就把 child 设置为最大的值的下标if (child + 1 < usedSize && elem[child + 1] > elem[child]) {//右子树比左子树大把 child + 1,就是右子树child += 1;}if (elem[parent] < elem[child]) {//进行交换swap(elem,child,parent);//调整完,把 parent 和 child 进行调整位置parent = child;child = parent * 2 + 1;}else {//这是 parent下标的值大于child,跳出break;}}}private void swap(int[] elem,int i,int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}
//这是我们的上次博客的代码。我们自实现的建立大根堆public void HeapSort() {//我们把第一个数据和最后一个数据进行交换//之后我们把 0 下标的值进行向下排序,这样之后我们会把大值放后面,小值放堆的前面int end = usedSize - 1;while (end > 0){swap(elem,0,end);shiftDown(0,end);end--;}}

     这就是我们的使用 大根堆进行排升序。对于 降序我们要使用建小堆来实现,我们和 用大堆实现升序就是思想是差不多的。


          ➷ 3、Top-k问题:

这个也是我们出现过的面试题。

                      ▶  Top-k的传送门:

                                       Top-k问题的最小k个数

     这个问题呢,就是求数据集合中前 k 个最大的元素或者是最小的元素,一般情况下呢都是数据比较多的情况下。

     我们对于这个问题呢,我们有三种不同的做法,假设我们有N个数据,我们来看:

1、直接排序,直接找到前 k 个。

2、建立一个我们有 N 个数据的堆,之后出前k个数据。

      就是如果求前 k 个最小的数据就是建小根堆。求前 k 个最大的数据就是建大根堆。

3、 比如我们求前k个最小的元素,我们执行:建立前k个大根堆,之后我们把N-K个元素和堆顶元         素进行比较,如果比堆顶的元素小,就把堆顶的数据删除,之后再把这个小的元素入堆

       对于求前k个最大的元素就是反之。(这个方法就是我们Top-k问题的最好的解决办法)

我们来看流程图:

    这样呢就是我们的最好的解决 Top-k 问题的思路了,之后理解这个之后呢,我们来看看我们的Top-k的代码如何编写:

java">class IntComp implements Comparator<Integer> {//这是把其变成大根堆@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}class Solution {public int[] smallestK(int[] arr, int k) {int[] ret = new int[k];if (arr == null || k == 0) {return ret;}//默认为小堆,我们传比较器PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,new IntComp());//把前k个元素放入到堆中for (int i = 0; i < k; i++) {priorityQueue.offer(arr[i]);}//之后从第 N-k 个数据开始比较知道比较结束//这里是求前k个最小的,所以把第 N-k 个数据和 堆顶进行比较,如果 N-k 小的话就是 删堆顶,入第N-k的元素堆for (int i = k; i < arr.length; i++) {int peekval = priorityQueue.peek();if (arr[i] < peekval) {priorityQueue.poll();priorityQueue.offer(arr[i]);}}//把堆里的元素放到数组中for (int i = 0; i < k; i++) {ret[i] = priorityQueue.poll();}return ret;}
}

    ※   注意:这里我们的 PriorityQueue 创建为什么要传参呢?因为我们默认的建堆方式是小根堆,我们是求前k个最小的元素,所以我们要建大根堆,所以我们要传比较器,使之变成大根堆。


  ❄️总结:

      OK,我们这次的博客就到这里就结束了,这里呢还是比较难理解的,所以我们要多进行练习一下,那么我们下次的博客呢,就开始接受我们的排序的问题了,这个排序还是很重要的,我们尽情期待吧!!!拜拜咯~~~


http://www.ppmy.cn/news/1529949.html

相关文章

docker 部署 禅道

拉取镜像 docker pull easysoft/zentao运行 docker run -d --name zentao -e ZT_MYSQL_HOSTxxx -e ZT_MYSQL_PORT3306 -e ZT_MYSQL_USERxxx -e ZT_MYSQL_PASSWORDxxx -e ZT_MYSQL_DBzen_tao_ss -p 80:80 easysoft/zentao注意 配置好mysql连接 参照 https://www.zentao.net…

力扣题解2376

大家好&#xff0c;欢迎来到无限大的频道。 今日继续给大家带来力扣题解。 题目描述&#xff08;困难&#xff09;&#xff1a; 统计特殊整数 如果一个正整数每一个数位都是 互不相同 的&#xff0c;我们称它是 特殊整数 。 给你一个 正 整数 n &#xff0c;请你返回区间 …

Python机器学习基础(NumPy、Pandas、Matplotlib)

Numpy函数库应用 NumPy 是 Python 中用于科学计算的核心库&#xff0c;它提供了高性能的多维数组对象以及用于处理这些数组的工具。 一、创建数组 1.使用array函数从 Python 列表或元组创建数组。 import numpy as np a np.array([1, 2, 3]) print(a) b np.array(…

快速理解TCP协议(三)——TCP协议的三次握手与四次挥手

在网络通信的浩瀚海洋中&#xff0c;TCP&#xff08;Transmission Control Protocol&#xff0c;传输控制协议&#xff09;如同一座坚固的桥梁&#xff0c;连接着网络世界的每一个角落。TCP协议通过其独特的三次握手&#xff08;Three-Way Handshake&#xff09;和四次挥手&…

期望Expectation的全概率公式

全概率公式是概率论中的一个公式&#xff0c;用于计算一个事件的期望值&#xff08;Expectation&#xff09;。期望值是随机变量的平均值&#xff0c;它反映了随机变量的中心趋势。 对于离散随机变量 X &#xff0c;其全概率公式为&#xff1a; E ( X ) ∑ i 1 n x i P ( X …

香港科技大学广州|金融科技学域博士招生宣讲会——武汉大学、华中科技大学

&#x1f514;&#x1f514;&#x1f514;明日宣讲&#x1f514;&#x1f514;&#x1f514; &#x1f490;香港科技大学广州&#xff5c;金融科技学域博士招生宣讲会 &#x1f4cd;武汉大学专场 &#x1f559;时间&#xff1a;2024年9月24日&#xff08;星期二&#xff09;1…

Android APN type 配置和问题

问题/疑问 如果APN配置了非法类型(代码没有定义的),则APN匹配加载的时候最终结果会是空类型。 那么到底是xml解析到数据库就是空type呢?还是Java代码匹配的时候映射是空的呢? Debug Log 尝试将原本的APN type加入ota或者新建一条ota type APN,检查log情况。 //Type有…

linux入门到实操-11 Linux时间日期指令

教程来源&#xff1a;B站视频BV1WY4y1H7d3 3天搞定Linux&#xff0c;1天搞定Shell&#xff0c;清华学神带你通关_哔哩哔哩_bilibili 整理汇总的课程内容笔记和课程资料&#xff08;包含课程同版本linux系统文件等内容&#xff09;&#xff0c;供大家学习交流下载&#xff1a;…