Java - 数组实现大顶堆
题目描述

实现思路
要实现一个堆,我们首先要了解堆的概念。
堆是一种完全二叉树,分为大顶堆和小顶堆。
-
大顶堆:每个节点的值都大于或等于其子节点的值。
-
小顶堆:每个节点的值都小于或等于其子节点的值。
完全二叉树:在一颗二叉树中,若除最后一层外的其余层都是满的,并且最后一层要么是满的,要么在右边缺少连续若干节点。

回到原题,实现一个大顶堆,使用数组作为底层数据结构,并提供以下操作:
-
添加元素(add):向堆中添加一个元素。
-
删除堆顶元素(poll):删除并返回堆顶元素(即最大值)。
首先我们需要明白一个事:
jdk提供的堆结构,也就是PriorityQueue优先级队列,删除堆顶元素(remove(),poll()),会进行下
沉操作,向最后插入元素(add(),offer()),会进行上浮操作,因为有这两个操作,所以在堆中,删除
堆顶元素,向最后插入元素不会改变堆结构。
但是向堆的中间进行插入或修改,就会改变堆结构,不会自己调整
所以我们实现堆,也得需要实现上浮和下沉操作
并且在上浮和下沉过程中,还需要交换元素,所以我们还需要实现一个数组中元素交换的函数
代码实现
class MaxHeap{//存储堆中元素的数组int[] heap;//堆中元素的个数int size;//堆的初始容量,超出容量,add函数里2倍扩容int capacity;public MaxHeap(int capacity) {this.capacity = capacity;heap = new int[capacity];size = 0;}public void add(int value) {//判断是否需要扩容if(size == capacity) {capacity = capacity * 2;int[] newHeap = new int[capacity];System.arraycopy(heap,0,newHeap,0,size);heap = newHeap;}heap[size] = value;size++;heapifyUp();}//上浮操作,维持堆的性质public void heapifyUp() {//当前节点对应在数组中的索引int index = size - 1;//父节点的在数组中的索引 -- 只能有一个父节点int parentIndex = (index - 1) / 2;while(parentIndex >= 0 && heap[parentIndex] < heap[index]) {swap(heap,parentIndex,index);index = parentIndex;parentIndex = (index - 1) / 2;}}//删除并返回堆顶元素public int poll() {//判断堆中是否有元素if(size == 0) {return Integer.MIN_VALUE;}int maxValue = heap[0];heap[0] = heap[size - 1];size--;heapifyDown();return maxValue;}//下沉操作,维持堆的性质public void heapifyDown() {int index = 0;//一个节点有两个子节点int leftChildIndex = 2 * index + 1;int rightChildIndex = 2 * index + 2;while(leftChildIndex < size) {//找到左右子节点中比较大的那个int largerChildIndex = leftChildIndex;if(rightChildIndex < size && heap[rightChildIndex] > heap[leftChildIndex]) {largerChildIndex = rightChildIndex;}//如果当前节点大于等于最大的子节点,堆性质已经满足if(heap[index] >= heap[largerChildIndex]) {break;}swap(heap,index,largerChildIndex);index = largerChildIndex;leftChildIndex = 2 * index + 1;rightChildIndex = 2 * index + 2;}}public void swap(int[] nums,int i,int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}
类似题目
【模板】堆_牛客题霸_牛客网
215. 数组中的第K个最大元素 - 力扣(LeetCode)
相关文章:
Java - 数组实现大顶堆
题目描述 实现思路 要实现一个堆,我们首先要了解堆的概念。 堆是一种完全二叉树,分为大顶堆和小顶堆。 大顶堆:每个节点的值都大于或等于其子节点的值。 小顶堆:每个节点的值都小于或等于其子节点的值。 完全二叉树ÿ…...
ifuse挂载后,在python代码中访问iOS沙盒目录获取app日志
上一次使用pymobiledevice3,在python代码中访问app的沙盒目录并分析业务日志,在使用过程中发现,在获取app日志的时候速度很慢,执行时间很长,需要30-61秒,所以这次尝试使用libimobiledevic和ifuse࿰…...
Windows WSL环境下安装 pytorch +ROCM 支持AMD显卡
官方文档:Install PyTorch for ROCm — Use ROCm on Radeon GPUs 一、操作系统及驱动 windows 下安装WSL 环境( windows subsystem for Linux), 安装ubuntu 22.04环境。 安装 rocm 软件包: sudo apt update wget https://repo.radeon.com/amdgpu-insta…...
uniapp中skymap.html(8100端口)提示未登录的排查与解决方法
问题: 目前账号已经登录,uniapp的其他端口均可以访问到数据,唯独skymap.html中的8100会提示未登录。(8100是后端网关gateway端口) 分析: 在 skymap.html 中遇到未登录提示的问题,通常是由于该…...
训练模型时梯度出现NAN或者INF(禁用amp的不同level)
判断参数梯度位nan或inf的代码: for name, param in model.named_parameters():if param.grad is not None:if torch.isnan(param.grad).any() or torch.isinf(param.grad).any():print(f"grad layer [{name}] is NaN or Inf") 首先来说可能得原因&…...
Maven核心概念
一、项目对象模型(POM) 1. 定义 POM(Project Object Model)是 Maven 项目的核心配置文件,它以 XML 格式描述了项目的基本信息、项目依赖、构建配置等。可以说,POM 是 Maven 理解和处理项目的基础。 2. 基…...
Sonatype Nexus 部署手册
文章目录 一、前言二、软件环境2.1 版本变更:2.1.1 变更存储的原因2.2.2 H2作为存储的注意点 三、资源配置四、开始部署4.1 部署jdk174.2 离线部署nexus4.2.1 下载4.2.2 部署1. 上传到服务器2. 解压3. 添加用户4. 修改启动参数5. 迁移sonatype-work ,并授…...
TLV320AIC3104IRHBR 数据手册 一款低功耗立体声音频编解码器 立体声耳机放大器芯片麦克风
TLV320AIC3104 是一款低功耗立体声音频编解码器,具有立体声耳机放大器以及在单端或全差分配置下可编程的多个输入和输出。该器件包括基于寄存器的全面电源控制,可实现立体声 48kHz DAC 回放,在 3.3V 模拟电源电压下的功耗低至 14mW࿰…...
(8)结构体、共用体和枚举类型数据
1. 结构体、共用体的定义及区别,typedef 定义别名 结构体的定义 结构体是一种用户自定义的数据类型,它可以将不同类型的数据组合在一起。例如,定义一个表示学生信息的结构体: // 定义结构体类型 struct Student struct Student {char name[20];int age;float score; };共…...
Jedis操作和springboot整合redis
Jedis-springboot整合redis Jedis 引入jedis依赖 注意事项 测试相关数据类型 Key String List set hash zset 案例 spring boot整合redis 引入相关依赖 在application.properties中配置redis 配置 创建redis配置类 创建测试类 Jedis 引入jedis依赖 <depen…...
基于AI大模型的复杂扫描件PDF信息提取与规整
前言 场景大致是会上传一个几十页的扫描件PDF,让AI在当中找出我需要的字段,本文会隐去具体行业信息和具体的AI提示词内容,只分享技术相关内容,请见谅。 AI模型选择 针对我们行业的使用场景,我主要测试了GPT、Claude以…...
为什么https先非对称加密,然后对称加密?
HTTPS之所以先使用非对称加密,然后在对称加密,主要是基于两者在加密效率与安全性方面的特性考虑。 首先,非对称加密具有极高的安全性,因为它使用了公钥和私钥这一对密钥。公钥是公开的,任何人都可以使用它来加密数据&…...
【Coroutines】Full Understanding of Kotlinx.Corutines Framework
文章目录 What is CorutinesDifference between Corutine and ThreadFast UsageSuspend FunctionAdvanced Usage of CoroutineCoroutine EssentialsCoroutineContextCoroutineScopePredefined CoroutineScopePredefined DispatchersPredefined CoroutineStartJobCreate a Corou…...
Python面向对象,实现图片处理案例,支持:高斯模糊、Canny边缘检测、反转边缘图像、生成手绘效果、调亮度......等等
实验图片如下: 命名为img1.jpg, 放在项目下新建文件夹images下 项目构造如下: app.py源码如下 import cv2 import os from matplotlib import pyplot as plt import numpy as npclass ImageProcessor:def __init__(self, image_path):self.image cv…...
SOLID - 依赖倒置原则(Dependency Inversion Principle)
SOLID - 依赖倒置原则(Dependency Inversion Principle) 定义 依赖倒置原则(Dependency Inversion Principle,DIP)是面向对象设计中的五大基本原则之一,通常缩写为SOLID中的D。DIP由Robert C. Martin提出&…...
【.NET 8 实战--孢子记账--从单体到微服务】--需求拆分与规划
在上一篇文章中我们收集了需求,并对需求进行了简单的分析和规划,但是对于开发人员来说,上一篇文章的需求还不够详细,并且没有形成计划。因此本篇文章将带领大家来拆分需求并规划开发里程碑。 一、详细需求列表 项目组进行了多次…...
在macOS的多任务处理环境中,如何平衡应用的性能与用户体验?这是否是一个复杂的优化问题?如何优化用户体验|多任务处理|用户体验|应用设计
目录 一 多任务处理与应用性能 1. macOS中的多任务处理机制 2. 性能优化的基本策略 二 用户体验的关键要素 1. 响应速度 2. 界面友好性 3. 功能的直观性 三 平衡性能与用户体验的策略 1. 资源管理 2. 优化数据加载 3. 使用合适的线程模型 4. 实时监测和调整 四 使…...
Vscode配置CC++编程环境的使用体验优化和补充说明
文章目录 快速编译运行👺code runner插件方案Code Runner Configuration 直接配置 相关指令和快捷键默认task配置和取消默认 配置文件补充介绍(可选 推荐阅读)😊使用vscode预置变量和环境变量环境变量的使用使用环境变量的好处环境变量可能引起的问题 检…...
十个方法杜绝CAD图纸泄密风险!2024年图纸防泄密指南!「必看」
随着信息技术的发展,CAD图纸的应用日益普遍,然而随之而来的图纸泄密风险也愈加严重。企业在提升效率的同时,更需重视信息安全。为此,本文将介绍十个有效的方法,帮助企业杜绝CAD图纸泄密风险,保障商业机密。…...
技术干货|HyperMesh CFD功能详解:虚拟风洞 Part 1
虚拟风洞VWT 从2023版本开始,虚拟风洞VWT(Virtual Wind Tunnel)模块合并到HyperMesh CFD中。 用户在VWT模块中完成LBM求解器ultraFluidX的前处理设置,导出参数文件XML和模型文件STL,并在GPU服务器上提交计算。 VWT目前…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
