堆-数组的堆化+优先队列(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

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

go中空接口的具体使用

《go中空接口的具体使用》空接口是一种特殊的接口类型,它不包含任何方法,本文主要介绍了go中空接口的具体使用,具有一定的参考价值,感兴趣的可以了解一下... 目录接口-空接口1. 什么是空接口?2. 如何使用空接口?第一,第二,第三,3. 空接口几个要注意的坑坑1:坑2:坑3:接口-空接口1. 什么是空接

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

Spring Boot3虚拟线程的使用步骤详解

《SpringBoot3虚拟线程的使用步骤详解》虚拟线程是Java19中引入的一个新特性,旨在通过简化线程管理来提升应用程序的并发性能,:本文主要介绍SpringBoot3虚拟线程的使用步骤,... 目录问题根源分析解决方案验证验证实验实验1:未启用keep-alive实验2:启用keep-alive扩展建

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子

GORM中Model和Table的区别及使用

《GORM中Model和Table的区别及使用》Model和Table是两种与数据库表交互的核心方法,但它们的用途和行为存在著差异,本文主要介绍了GORM中Model和Table的区别及使用,具有一... 目录1. Model 的作用与特点1.1 核心用途1.2 行为特点1.3 示例China编程代码2. Tab

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp