当前位置: 首页 > news >正文

【数据结构】堆,优先级队列

目录

  • 堆的性质
  • 大根堆的模拟实现
    • 接口实现
    • 构造方法
    • 建堆
    • 入堆
    • 判满
    • 删除
    • 判空
    • 获取堆顶元素
  • Java中的PriorityQueue
    • 实现的接口
    • 构造方法
    • 常用方法
    • PriorityQueue注意事项
  • 练习

如果有一个集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质

  • 堆逻辑结构上是一棵完全二叉树。
  • 堆上的节点一定不大于(大根堆)或者不小于(小根堆)父亲节点。

大根堆的模拟实现

使用代码来实现一个大根堆。

接口实现

接口成员方法。

public class PriorityQueue {public int[] elem;public int usedSize;public PriorityQueue() {}//建堆public void createHeap(int[] array) {}/*** @param root 是每棵子树的根节点的下标* @param len  是每棵子树调整结束的结束条件* 向下调整的时间复杂度:O(logn)*/private void shiftDown(int root,int len) {}// 入堆:仍然要保持是大根堆public void push(int val) {}private void shiftUp(int child) {}//判断堆是否满public boolean isFull() {}//每次删除的都是优先级高的元素,删除后任是大根堆public void pollHeap() {}//判断堆是否为空public boolean isEmpty() {}// 获取堆顶元素public int peekHeap() {}
}

构造方法

在构造方法中构建为长度10的数组。

public PriorityQueue() {elem = new int[10];}

建堆

createHeap思路:

  1. 先将数组拷贝进成员数组中(注意看长度是否够)。
  2. 我们从最后一棵子树的根节点开始调用shiftDown方法向上一棵一棵树的调整为大根堆。

shiftDown思路:

  1. 将当前传入的根节点与他的孩子节点将最大值选出作为根。
  2. 然后将根变成孩子节点再次调整。
  3. 注意挑选最大值的时候要判断不能让下标越界。
 public void createHeap(int[] array) {if(elem.length < array.length){elem = Arrays.copyOf(elem, elem.length * 2);}for (int i = 0; i < array.length; i++){elem[i] = array[i];usedSize++;}for (int root = (usedSize -1 -1) / 2; root >= 0 ; root--) {shiftDown(root,usedSize);}}/*** @param root 是每棵子树的根节点的下标* @param len  是每棵子树调整结束的结束条件* 向下调整的时间复杂度:O(logn)*/private void shiftDown(int root,int len) {int child = root * 2 + 1;while (child < len){//寻找孩子节点的大值if(child + 1 < len && elem[child] < elem[child + 1]){child++;}if(elem[root] < elem[child]){swap(elem,root,child);root = child;child = root * 2 + 1;}else {break;}}}//交换函数private void swap(int[] array,int x,int y){int tmp = array[x];array[x] = array[y];array[y] = tmp;}

入堆

代码思路:

  1. 先判断堆是否已经满了,满了要扩容。
  2. 在堆最后存入该元素,然后与父亲节点相比较,比父亲节点大就交换,直到到根节点或者比父亲节点小为止。
	 /*** 入堆:仍然要保持是大根堆* @param val*/public void push(int val) {if(isFull()){elem = Arrays.copyOf(elem, elem.length*2);}elem[usedSize] = val;shiftUp(usedSize);usedSize++;}private void shiftUp(int child) {int parent = (child - 1) / 2;while(parent >= 0) {if (elem[parent] < elem[child]) {swap(elem, parent, child);child = parent;parent = (child - 1) / 2;}else {break;}}}

判满

这个方法直接使用成员变量usedSize和数组长度判断即可。

public boolean isFull() {return usedSize == elem.length;}

删除

代码思路:

  1. 先判断堆是否为空,为空直抛空指针异常。
  2. 我们先将堆顶和堆尾交换,然后向下调整一次。
  3. useds减1。
ublic void pollHeap() throws NullPointerException {if (isEmpty()) {throw new NullPointerException();}swap(elem,0,usedSize-1);shiftDown(0,usedSize);usedSize--;}

判空

这个方法直接使用成员变量usedSize是否为0就行。

public boolean isEmpty() {return usedSize == 0;}

获取堆顶元素

如果堆为空,抛空指针异常,没有直接返回堆顶元素。

public int peekHeap() throws NullPointerException {if (isEmpty()) {throw new NullPointerException();}return elem[0];}

Java中的PriorityQueue

在Java中使用集合类PriorityQueue来表示优先级队列,其底层是一个小根堆。

实现的接口

构造方法

提供了以下3种构造方法:

方法方法用途介绍
PriorityQueue()创建一个空的优先级队列,默认容量是11
PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列,注意initialCapacity不能小于1,否则会抛IllegalArgumentException异常
PriorityQueue(Collection<? extends E> c)用一个集合来创建优先级队列

常用方法

常用方法如下:

PriorityQueue注意事项

  1. 使用要导包import java.util.PriorityQueue;
  2. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出ClassCastException异常。
  3. 不能插入null对象,否则会抛出NullPointerException
  4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容。
  5. 如果要将PriorityQueue变成一个大根堆,类实现Comparator后重写 compare方法时将比较改为
public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}

练习

最小k个数

相关文章:

【数据结构】堆,优先级队列

目录 堆堆的性质大根堆的模拟实现接口实现构造方法建堆入堆判满删除判空获取堆顶元素 Java中的PriorityQueue实现的接口构造方法常用方法PriorityQueue注意事项 练习 堆 如果有一个集合K {k0&#xff0c;k1&#xff0c; k2&#xff0c;…&#xff0c;kn-1}&#xff0c;把它的…...

2024 暑假友谊赛 2

Tree Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路:LCA好题&#xff0c;也有看见用时间戳写的&#xff0c;不是很明白. 用LCA非常好写。 要想到,给出k个节点&#xff0c;要确定一条路径&#xff0c;使得给出的k个点要么在路径上&#xff0c;要么和路径中某点的…...

c++ 线程

在 C 中&#xff0c;std::thread 构造函数可以用于将参数传递给线程。这里是一个基本的示例&#xff0c;展示了如何使用 std::thread 来传递参数&#xff1a; #include <iostream> #include <thread>// 定义一个被线程调用的函数 void threadFunc(int arg1, doubl…...

【SpringBoot】URL映射之consumes和produces匹配、params和header匹配

4.2.3 consumes和produces匹配 //处理request Content-Type为"application/json"类型的请求 RequestMapping(value"/Content",methodRequestMethod.POST,consumes"application/json") public String Consumes(RequestBody Map param){ return…...

vscode配置django环境并创建django项目(全图文操作)

文章目录 创建项目工作路径下载python插件&#xff1a;创建虚拟环境1. 命令方式创建2. 图文方式创建 在虚拟环境中安装Django创建Django项目安装Django插件选择虚拟环境 创建项目工作路径 输入 code . 下载python插件&#xff1a; 创建虚拟环境 1. 命令方式创建 切换在工作目…...

(一)延时任务篇——延时任务的几种实现方式概述

前言 延时任务是我们在项目开发中经常遇到的场景&#xff0c;例如订单超时30分钟自动取消&#xff0c;邮件5分钟后通知等等&#xff0c;对于这样的应用场景&#xff0c;我们又该如何应对呢&#xff0c;尤其是在微服务环境下&#xff0c;如何保证我们的延迟任务并发问题以及数据…...

每天五分钟计算机视觉:目标检测模型从RCNN到Fast R-CNN的进化

本文重点 前面的课程中,我们学习了RCNN算法,但是RCNN算法有些慢,然后又有了基于RCNN的Fast-RCNN,Fast R-CNN是一种深度学习模型,主要用于目标检测任务,尤其在图像中物体的识别和定位方面表现出色。它是R-CNN系列算法的一个重要改进版本,旨在解决R-CNN中计算量大、速度慢…...

环境变量配置文件中两种路径添加方式

环境变量配置文件中两种路径添加方式 文章目录 环境变量配置文件中两种路径添加方式代码示例区别和作用 代码示例 export HBASE_HOME/opt/software/hbase-2.3.5 export PATH$PATH:$HBASE_HOME/binexport SPARK_HOME/opt/software/spark-3.1.2 export PATH$SPARK_HOME/bin:$PAT…...

开放系统互连安全体系结构学习笔记总结

开篇 本文是《网络安全 技术与实践》一书中序章中“开放系统互连安全体系结构”这一块的笔记总结。 定义 开放系统互连&#xff08;Open System Interconnection, OSI&#xff09;安全体系结构定义了必需的安全服务、安全机制和技术管理&#xff0c;以及它们在系统上的合理部署…...

linux搭建redis cluster集群

集群介绍: Redis 集群实现了对Redis的水平扩容,即启动N个redis节点,将整个数据库分布存储在这N个节点中,每个节点存储总数据的1/N。 Redis 集群通过分区(partition)来提供一定程度的可用性(availability): 即使集群中有一部分节点失效或者无法进行通讯, 集群也可以继…...

瀚高数据库初级考试认证

pg_dumpall可以转储全局角色和表空间信息 单选题2分 A. 是 B. 否 回答正确(2分) 答案&#xff1a; A 解析&#xff1a;pg_dumpall备份一个给定集簇中的每一个数据库&#xff0c;并且也保留了集簇范围的数据&#xff0c;如角色和表空间定义。 2. 自定义文件格式必须与pg_restore…...

【java基础】spring中使用到的设计模式

Spring框架在其设计和实现中使用了多种设计模式&#xff0c;这些模式帮助Spring框架保持灵活性、可扩展性和易于集成的特点。以下是一些在Spring框架中常见和重要的设计模式&#xff1a; 工厂模式&#xff08;Factory Pattern&#xff09; Spring的核心容器使用了工厂模式&…...

浅层深度学习的概述

在人工智能和机器学习的领域中&#xff0c;“深度学习”已成为一个热门话题。该术语通常与多层神经网络和复杂模型联系在一起&#xff0c;然而&#xff0c;“浅层深度学习”是指那些较为简单而且通常只有一两个隐藏层的神经网络。这种模型在许多任务中表现出色&#xff0c;同时…...

如何找到最快解析速度的DNS

如何找到最快解析速度的DNS DNS,即域名系统(Domain Name System),是互联网的一项服务。它作为将域名和IP地址相互映射的一个分布式数据库,能够使用户更方便地访问互联网,而不用记住能够被机器直接读取的IP数串。 在浏览网页时,我们通常使用域名,而不是IP地址。当域名在…...

【YashanDB知识库】数据库使用shutdown immediate无响应导致coredump

【标题】数据库使用shutdown immediate无响应导致coredump 【问题分类】数据库维护 【关键词】YashanDB, shutdown immediate, coredump 【问题描述】执行shutdown immediate后&#xff0c;数据库一直没有退出&#xff0c;在操作系统层面强制停止数据库进程时发生coredump。…...

web前端 React 框架面试200题(一)

面试题 1. 简述什么是React &#xff08; 概念 &#xff09;&#xff1f; 参考回答&#xff1a; 1、React是Facebook开发的一款JS库。 2、React一般被用来作为MVC中的V层&#xff0c;它不依赖其他任何的库&#xff0c;因此开发中&#xff0c;可以与任何其他的库集成使用&…...

【前端】JavaScript入门及实战91-95

文章目录 91 DOM92 事件93 文档的加载94 DOM查询(1)95 图片切换的练习 91 DOM <!DOCTYPE html> <html> <head> <title></title> <meta charset"utf-8"><style> </style> </head> <body><button id&…...

vue3在元素上绑定自定义事件弹出虚拟键盘

最近开发中遇到一个需求: 焊接机器人的屏幕上集成web前端网页, 但是没有接入键盘。这就需要web端开发一个虚拟键盘,在网上找个很多虚拟键盘没有特别适合,索性自己写个简单的 图片: 代码: (代码可能比较垃圾冗余,也没时间优化,凑合看吧) 第一步:创建键盘组件 为了方便使用…...

VMware 上安装 CentOS 7 教程 (包含网络设置)

**建议先看一些我安装VMware的教程&#xff0c;有些网络配置需要做一下 1.打开VMware&#xff0c;创建虚拟机 2.勾选自定义&#xff0c;点击下一步 3.点击下一步 4.勾选“稍后安装操作系统”&#xff0c;点击下一步 5.勾选linux&#xff0c;勾选centos7&#xff0c;点击下一步…...

算法 day4 【双指针、快慢指针、环形链表】链表下

⚡刷题计划day4继续&#xff0c;可以点个免费的赞哦~ 下一期将会开启哈希表刷题专题&#xff0c;往期可看专栏&#xff0c;关注不迷路&#xff0c; 您的支持是我的最大动力&#x1f339;~ 目录 ⚡刷题计划day4继续&#xff0c;可以点个免费的赞哦~ 下一期将会开启哈希表刷题…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

ABB馈线保护 REJ601 BD446NN1XG

配电网基本量程数字继电器 REJ601是一种专用馈线保护继电器&#xff0c;用于保护一次和二次配电网络中的公用事业和工业电力系统。该继电器在一个单元中提供了保护和监控功能的优化组合&#xff0c;具有同类产品中最佳的性能和可用性。 REJ601是一种专用馈线保护继电器&#xf…...

【芯片仿真中的X值:隐藏的陷阱与应对之道】

在芯片设计的世界里&#xff0c;X值&#xff08;不定态&#xff09;就像一个潜伏的幽灵。它可能让仿真测试顺利通过&#xff0c;却在芯片流片后引发灾难性后果。本文将揭开X值的本质&#xff0c;探讨其危害&#xff0c;并分享高效调试与预防的实战经验。    一、X值的本质与致…...