堆-数组的堆化+优先队列(PriorityQueue)的使用

2024-09-08 05:12

本文主要是介绍堆-数组的堆化+优先队列(PriorityQueue)的使用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、堆

1、什么是堆?

以完全二叉树的形式将元素存储到对应的数组位置上所形成的新数组

2、为什么要将数组变成堆?

当数组中的元素连续多次进行排序时会消耗大量的时间,将数组变成堆后通过堆排序的方式将会消耗更少的时间

二、接口

给堆定义一个接口,用来规范堆里面的方法

1、在获取堆顶元素和删除堆顶元素的方法中,都必须返回堆顶元素,当堆为空时,返回异常对象要比返回null关键字更加安全

定义堆异常类

package com.ffyc.heap;/*** 自定义堆异常 继承RuntimException而不继承Exception的原因是RuntimException在遇到异常时JVM会自动捕捉异常异常,而Exception必须使用try catch或者throws手动处理异常*/
public class HeapException extends RuntimeException{public HeapException(String message) {super(message);}
}

三、数组的堆化

这里的时间复杂度是将堆作为满二叉树计算出来的

1、方法一:逐个添加元素创建堆

(1)的高度为h,进行上浮和下沉操作最大时间与高度h有关,时间复杂度为O(h)

(2)是一棵完全二叉树,完全二叉树的时间复杂度与结点有关O(log_{2}^{n}),此处n为二叉树的结点数目

(3)对堆中一个数据进行上浮和下沉操作的时间复杂度均为O(h)=O(log_{2}^{n})

(4)通过逐个添加元素创建堆的方式来创建堆的时间复杂度为O(nlog_{2}^{n})

2、方法二:将外界数组调整成堆(堆化)

使用逐个添加元素的方式创建堆可能会出现索引越界的问题,为了解决索引越界的问题,我们可以采用动态数组扩容的方式,但是由于不知道到底数组大小要扩到什么程度,因此会损失一部分时间和空间,降低了程序运行效率。如果我们直接将外界传进来的数组调整成堆,即对数组进行堆化,这将会避免由于数组容量不足所带来的索引越界问题

1、使用Integer.MAX_VALUE创建数组

/*** 运行程序会报异常java.lang.OutOfMemoryError,表明在JVM中创建的数组大小超出了JVM配置的最大限制,* 即JVM的堆空间(Heap space)不足以容纳下这个数组*/int[]a=new int[Integer.MAX_VALUE];

2、heapify(堆化)的平均时间复杂度=每层结点数*移动数=O(2^{h}-h-1)=O(2^{h})=O(n)

四、优先队列-PriorityQueue

1、PriorityQueue底层默认使用最小堆实现

public PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}

2、PriorityQueue底层提供的将最小堆实现优先队列转为最大堆实现优先队列的方法

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

3、PriorityQueue底层提供的将外界传入的集合直接进行堆化的方法

 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底层提供的将外界传入的集合进行堆化的方法

public boolean addAll(Collection<? extends E> c) {if (c == null)throw new NullPointerException();if (c == this)throw new IllegalArgumentException();boolean modified = false;for (E e : c)if (add(e))modified = true;return modified;}

5、集合堆化的三种形式

(1)创建最小堆,调用addAll方法堆化集合

public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(9);list.add(2);list.add(5);list.add(8);list.add(3);// 创建最小堆,调用addAll方法堆化集合PriorityQueue<Integer>priorityQueue=new PriorityQueue<>();// 将list集合进行堆化priorityQueue.addAll(list);// 获取堆顶元素System.out.println(priorityQueue.peek());// 删除堆顶元素priorityQueue.poll();System.out.println(priorityQueue.peek());}

(2) 创建最小堆,直接堆化集合

public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(9);list.add(2);list.add(5);list.add(8);list.add(3);// 创建最小堆,直接堆化集合PriorityQueue<Integer>priorityQueue=new PriorityQueue<>(list);// 获取堆顶元素System.out.println(priorityQueue.peek());// 删除堆顶元素priorityQueue.poll();System.out.println(priorityQueue.peek());}

(3)创建最大堆,调用addAll方法堆化集合

 public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(9);list.add(2);list.add(5);list.add(8);list.add(3);// 创建底层由最大堆实现的优先队列(使用匿名内部类作为参数,可用idea工具将其转换为lambda)PriorityQueue<Integer>priorityQueue=new PriorityQueue<>(Comparator.reverseOrder());// 将list集合进行堆化priorityQueue.addAll(list);// 获取堆顶元素System.out.println(priorityQueue.peek());// 删除堆顶元素priorityQueue.poll();System.out.println(priorityQueue.peek());}
 

这篇关于堆-数组的堆化+优先队列(PriorityQueue)的使用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1147210

相关文章

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Maven的使用和配置国内源的保姆级教程

《Maven的使用和配置国内源的保姆级教程》Maven是⼀个项目管理工具,基于POM(ProjectObjectModel,项目对象模型)的概念,Maven可以通过一小段描述信息来管理项目的构建,报告... 目录1. 什么是Maven?2.创建⼀个Maven项目3.Maven 核心功能4.使用Maven H

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

Spring Boot 集成 Quartz并使用Cron 表达式实现定时任务

《SpringBoot集成Quartz并使用Cron表达式实现定时任务》本篇文章介绍了如何在SpringBoot中集成Quartz进行定时任务调度,并通过Cron表达式控制任务... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启动 Sprin

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

使用Python实现一个优雅的异步定时器

《使用Python实现一个优雅的异步定时器》在Python中实现定时器功能是一个常见需求,尤其是在需要周期性执行任务的场景下,本文给大家介绍了基于asyncio和threading模块,可扩展的异步定... 目录需求背景代码1. 单例事件循环的实现2. 事件循环的运行与关闭3. 定时器核心逻辑4. 启动与停