java中的PriorityQueue类过程详解

目录
  • 一、什么是优先级队列
    • 1、概念
    • 2、案例演示特性
    • 3、数据结构

一、什么是优先级队列

1、概念

我们都知道队列，队列的核心思想就是先进先出，这个优先级队列有点不太一样。优先级队列中，数据按关键词有序排列，插入新数据的时候，会自动插入到合适的位置保证队列有序。（顺序有两种形式：升序或者是降序）

来一个标准点的定义：

PriorityQueue类在Java1.5中引入。PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。

比如我们往队列里面插入132，插入2的时候，就会在内部调整为123（默认顺序是升序）。正是由于这个优良特性可以帮助我们实现一系列问题。我们先看一个例子，体会一下他的优点，然后再看一下为什么能够实现这样的功能。

我们看到就算是我们随意插入数据，但是输出的结果总是有序的，这样一来优先级队列就可以有了很多个使用场景。下面给出一道力扣题。体会一下他的优点。

2、案例演示特性

Leetcode215题：在未排序的数组中找到第 k个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

输入：3,2,3,1,2,4,5,5,6，k = 4。输出就是5，因此重复的并不考虑。我们一般情况下一般首先想到冒泡排序。每一次都冒出来一个最小的元素，这样冒K次，就是我们想要的结果。

其实冒泡排序还可以解决另外一个问题，那就是返回倒数第K大的元素，方法是每次冒出来一个最大的元素即可。

这样做很简单，但是需要我们自己手写冒泡排序，下面我们看使用优先级队列如何解决的。

就这几行代码就搞定了，是不是超级简单。为什么优先级队列能够实现呢？下面我们来分析一下他的数据结构：

3、数据结构

优先级队列底层的数据结构其实是一颗二叉堆，什么是二叉堆呢？我们来看看

在这里我们会发现以下特征：

（1）二叉堆是一个完全二叉树

（2）根节点总是大于左右子节点（大顶堆），或者是小于左右子节点（小顶堆）。

如果我们要插入一个节点怎么办呢？

自己使用画图工具画的，能看懂就行，不要在意那些细节兄弟。过程如下：

（1）找到待插入位置：满足完全二叉树的特点，依次插入

（2）插入之后判断是否满足二叉堆的性质，不满足那就调整

（3）1<>6交换，发现不满足，1<>4交换，满足即停止。

对于我们的优先级队列就是这样的一种数据结构，因此我们在插入的时候保证了数据的有序性。

OK。到这基本上我们能够体会到优先级队列的思想了。来一个小结：

优先级队列使用二叉堆的特点，可以使得插入的数据自动排序（升序或者是降序）。

到此这篇关于java中的PriorityQueue类的文章就介绍到这了,更多相关java PriorityQueue类内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • java 单元测试 对h2数据库数据清理方式

    目录 java 单元测试 对h2数据库数据清理 前因 junit单元测试使用H2内存数据库 首先导入H2内存数据库 其次使用H2数据源模拟Oracle 下面来写个Junit4的单元测试类例子 java 单元测试 对h2数据库数据清理 前因 写测试框架的时候使用的精简测试框架不需要启动整个springboot,并不支持@Transactional测试后回滚h2数据库,而是在基础测试类里声明cleandb函数供使用,这就需要适配任意表的数据清除,不过更推荐不清理,以方法名为id使数据不重复即可 tr

  • Java 如何读取Excel格式xls、xlsx数据工具类

    Java 如何读取Excel格式xls、xlsx数据工具类

    目录 Java 读取Excel格式xls.xlsx数据工具类 需要POI的jar包支持 调用方式 使用poi读取xlsx格式的Excel总结 今天遇到的坑 我使用的是springmvc,首先是controller部分 然后是读取Excel文件部分,也就是service部分 spring-servlet.xml 配置如下 最初的maven是这么配置的 Java 读取Excel格式xls.xlsx数据工具类 需要POI的jar包支持 调用方式 ReadExcelTest excelTest = ne

  • Java之JSF框架案例详解

    Java之JSF框架案例详解

    这是一个分为两部分的系列,其中我介绍了JSF 2及其如何适合Java EE生态系统. 在第1部分中,我将介绍JavaServer Pages(JSF)背后的基本思想 ,在第2部分中,将介绍Facelets声明语言 . 在构建Web应用程序时,我们为最终用户提供了一种与我们的应用程序进行交互的方式,这就是JSF所提供的. 我将向您介绍MVC设计模式以及如何使用它,并且您将发现Facelets视图语言及其使用方式,如何将数据和事件绑定到上下文以及如何通过表达语言来实现. 我将通过查看替代模板框架(例

  • Java详解HashMap实现原理和源码分析

    Java详解HashMap实现原理和源码分析

    目录 学习要点: 1.什么是HashMap? 2.HashMap的特性 3.HashMap的数据结构 4.HashMap初始化操作 4.1.成员变量 4.2. 构造方法 5.Jdk8中HashMap的算法 5.1.HashMap中散列算法 5.2.什么是HashMap中哈希冲突? 6.Jdk8中HashMap的put操作 7.HashMap的扩容机制 7.1.什么时候需要扩容? 7.2.什么是HashMap的扩容? 7.3.resize的源码实现 8.Jdk8中HashMap的remove操作

  • JAVA Spring中让人头痛的JAVA大事务问题要如何解决你知道吗

    JAVA Spring中让人头痛的JAVA大事务问题要如何解决你知道吗

    目录 前言 大事务引发的问题 解决办法 少用@Transactional注解 将查询(select)方法放到事务外 事务中避免远程调用 事务中避免一次性处理太多数据 非事务执行 总结 前言 最近有个网友问了我一个问题:系统中大事务问题要如何处理? 正好前段时间我在公司处理过这个问题,我们当时由于项目初期时间比较紧张,为了快速完成业务功能,忽略了系统部分性能问题.项目顺利上线后,专门抽了一个迭代的时间去解决大事务问题,目前已经优化完成,并且顺利上线.现给大家总结了一下,我们当时使用的一些解决办法,

  • Java使用EasyExcel动态添加自增序号列

    Java使用EasyExcel动态添加自增序号列

    目录 前言 实现 思路 其它 总结 前言 本文将介绍如何通过使用EasyExcel自定义拦截器实现在最终的Excel文件中新增一列自增的序号列,最终的效果如下: 此外,本文所使用的完整代码示例已上传到GitHub. 实现 本文主要是通过自定义一个继承AbstractRowWriteHandler的拦截器来实现在最终导出的结果中新增序号列,通过修改源码中保存头部标题的Map内容来给自己添加的序号列留出位置,先展示最终的代码: /** * 自定义 excel 行处理器, 增加序号列 * * @aut

  • java中的PriorityQueue类过程详解

    java中的PriorityQueue类过程详解

    目录 一.什么是优先级队列 1.概念 2.案例演示特性 3.数据结构 一.什么是优先级队列 1.概念 我们都知道队列,队列的核心思想就是先进先出,这个优先级队列有点不太一样.优先级队列中,数据按关键词有序排列,插入新数据的时候,会自动插入到合适的位置保证队列有序.(顺序有两种形式:升序或者是降序) 来一个标准点的定义: PriorityQueue类在Java1.5中引入.PriorityQueue是基于优先堆的一个无界队列,这个优先队列中的元素可以默认自然排序或者通过提供的Comparator(

  • java 中enum的使用方法详解

    java 中enum的使用方法详解 enum 的全称为 enumeration, 是 JDK 1.5 中引入的新特性,存放在 java.lang 包中. 下面是我在使用 enum 过程中的一些经验和总结. 原始的接口定义常量 public interface IConstants { String MON = "Mon"; String TUE = "Tue"; String WED = "Wed"; String THU = "Thu

  • java中Spring Security的实例详解

    java中Spring Security的实例详解

    java中Spring Security的实例详解 spring security是一个多方面的安全认证框架,提供了基于JavaEE规范的完整的安全认证解决方案.并且可以很好与目前主流的认证框架(如CAS,中央授权系统)集成.使用spring security的初衷是解决不同用户登录不同应用程序的权限问题,说到权限包括两部分:认证和授权.认证是告诉系统你是谁,授权是指知道你是谁后是否有权限访问系统(授权后一般会在服务端创建一个token,之后用这个token进行后续行为的交互). spring

  • 多用多学之Java中的Set,List,Map详解

    很长时间以来一直代码中用的比较多的数据列表主要是List,而且都是ArrayList,感觉有这个玩意就够了.ArrayList是用于实现动态数组的包装工具类,这样写代码的时候就可以拉进拉出,迭代遍历,蛮方便的. 也不知道从什么时候开始慢慢的代码中就经常会出现HashMap和HashSet之类的工具类.应该说HashMap比较多一些,而且还是面试经典题,平时也会多看看.开始用的时候简单理解就是个键值对应表,使用键来找数据比较方便.随后深入了解后发现 这玩意还有点小奥秘,特别是新版本的JDK对Has

  • JAVA DOM解析XML文件过程详解

    JAVA DOM解析XML文件过程详解

    这篇文章主要介绍了JAVA DOM解析XML文件过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 import java.io.IOException; import javax.xml.parsers.*; import org.w3c.dom.Document; import org.w3c.dom.Element; import org.w3c.dom.NamedNodeMap; import org.w3c.dom.No

  • Java中Lambda表达式的使用详解

    目录 理解函数式接口以及 Lambda表达式的发展过程 Lambda表达式及语法 一起来看看具体的使用 你需要注意什么 Lambda的实际运用 1.对集合排序 2.遍历集合 3.遍历集合(带条件) 4.代替 Runnable,开启一个线程 理解函数式接口以及 Lambda表达式的发展过程 任何接口,只包含唯一一个抽象方法,就是函数式接口 /** * lambdab表达式的发展 */ public class TestLambda1 { //3.静态内部类 static class Like2 i

  • Java中的反射机制示例详解

    Java中的反射机制示例详解

    目录 反射 什么是Class类 获取Class实例的三种方式 通过反射创建类对象 通过反射获取类属性.方法.构造器 更改访问权限和实例赋值 运用场景 反射 反射就是把Java类中的各个成分映射成一个个的Java对象.即在运行状态中,对于任意一个类,都能够知道这个类的所以属性和方法:对于任意一个对象,都能调用它的任意一个方法和属性.这种动态获取信息及动态调用对象方法的功能叫Java的反射机制 每一个Java程序执行必须通过编译.加载.链接和初始化四个阶段 1.编译:将.java.文件编译成字节码.

  • Java中随机函数变换的示例详解

    Java中随机函数变换的示例详解

    目录 说明 解决的问题 问题1 问题2 问题3 问题4 说明 本示例中基于 Java ,其他语言也有类似的 API 解决的问题 问题1 Java 中 Math.random()函数是等概率返回区间[0,1)中的任意一个小数.即x < 1情况下,[0,x)中的数出现的的概率是x,如果我们要将x < 1情况下,[0,x)中的数出现的的概率调整成x^2,应该如何做? 问题1思路 由于[0,x)的概率是x,那么调用两次Math.random(),如果较大的那个值也要在[0,x)区间内,那么两次调用都必

  • Java中注解与原理分析详解

    Java中注解与原理分析详解

    目录 一.注解基础 二.注解原理 三.常用注解 1.JDK注解 2.Lombok注解 四.自定义注解 1.同步控制 2.类型引擎 一.注解基础 注解即标注与解析,在Java的代码工程中,注解的使用几乎是无处不在,甚至多到被忽视: 无论是在JDK源码或者框架组件,都在使用注解能力完成各种识别和解析动作:在对系统功能封装时,也会依赖注解能力简化各种逻辑的重复实现: 基础接口 在Annotation的源码注释中有说明:所有的注解类型都需要继承该公共接口,本质上看注解是接口,但是代码并没有显式声明继承关

  • Java 中This用法的实例详解

     Java 中This用法的实例详解 用类名定义一个变量的时候,定义的只是一个引用,外面可以通过这个引用来访问这个类里面的属性和方法. 那们类里面是够也应该有一个引用来访问自己的属性和方法纳? 呵呵,Java提供了一个很好的东西,就是 this 对象,它可以在类里面来引用这个类的属性和方法.先来个简单的例子: public class ThisDemo { String name="Mick"; public void print(String name){ System.out.pr

随机推荐