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

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while