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

相关文章

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

如何使用Spring boot的@Transactional进行事务管理

《如何使用Springboot的@Transactional进行事务管理》这篇文章介绍了SpringBoot中使用@Transactional注解进行声明式事务管理的详细信息,包括基本用法、核心配置... 目录一、前置条件二、基本用法1. 在方法上添加注解2. 在类上添加注解三、核心配置参数1. 传播行为(

在Java中使用ModelMapper简化Shapefile属性转JavaBean实战过程

《在Java中使用ModelMapper简化Shapefile属性转JavaBean实战过程》本文介绍了在Java中使用ModelMapper库简化Shapefile属性转JavaBean的过程,对比... 目录前言一、原始的处理办法1、使用Set方法来转换2、使用构造方法转换二、基于ModelMapper

c++中std::placeholders的使用方法

《c++中std::placeholders的使用方法》std::placeholders是C++标准库中的一个工具,用于在函数对象绑定时创建占位符,本文就来详细的介绍一下,具有一定的参考价值,感兴... 目录1. 基本概念2. 使用场景3. 示例示例 1:部分参数绑定示例 2:参数重排序4. 注意事项5.

使用C++将处理后的信号保存为PNG和TIFF格式

《使用C++将处理后的信号保存为PNG和TIFF格式》在信号处理领域,我们常常需要将处理结果以图像的形式保存下来,方便后续分析和展示,C++提供了多种库来处理图像数据,本文将介绍如何使用stb_ima... 目录1. PNG格式保存使用stb_imagephp_write库1.1 安装和包含库1.2 代码解

一文教你使用Python实现本地分页

《一文教你使用Python实现本地分页》这篇文章主要为大家详细介绍了Python如何实现本地分页的算法,主要针对二级数据结构,文中的示例代码简洁易懂,有需要的小伙伴可以了解下... 在项目开发的过程中,遇到分页的第一页就展示大量的数据,导致前端列表加载展示的速度慢,所以需要在本地加入分页处理,把所有数据先放

Spring Boot Actuator使用说明

《SpringBootActuator使用说明》SpringBootActuator是一个用于监控和管理SpringBoot应用程序的强大工具,通过引入依赖并配置,可以启用默认的监控接口,... 目录项目里引入下面这个依赖使用场景总结说明:本文介绍Spring Boot Actuator的使用,关于Spri

Java中基于注解的代码生成工具MapStruct映射使用详解

《Java中基于注解的代码生成工具MapStruct映射使用详解》MapStruct作为一个基于注解的代码生成工具,为我们提供了一种更加优雅、高效的解决方案,本文主要为大家介绍了它的具体使用,感兴趣... 目录介绍优缺点优点缺点核心注解及详细使用语法说明@Mapper@Mapping@Mappings@Co

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、