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

数据结构手撕--【堆】

news 来源：原创 2025/6/18 22:24:30

编辑

定义结构体：

初始化：

插入数据：

删除：

取堆顶元素：

堆销毁：

判断堆是否为空：

TopK问题：

堆其实是完全二叉树

物理结构：二叉树的层序遍历（顺序存储）

逻辑结构：完全二叉树

定义结构体：

typedef int HPDataType;
typedef struct heap
{HPDataType* a; //数组指针（指向一块空间）int size; //有效数据个数int capacity; //最多可以存的数据个数
}Heap;

初始化：

void HeapInit(Heap* hp)
{assert(hp);hp->a = NULL;hp->size = hp->capacity = 0;
}

插入数据：

放到最后一个 + 向上调整

向上调整：

void AdjustUp(HPDataType* a, int child)//传进来堆空间 和孩子下标----这个是最后一个节点
{int parent = (child - 1) / 2;while (child > 0){if (a[parent] > a[child]){swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->size == hp->capacity){int newcapacity = hp->capacity == 0 ? 4 : (hp->capacity) * 2;HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}hp->a = tmp;hp->capacity = newcapacity;}hp->a[hp->size] = x;size++;//向上调整 --- 向上调整为一个小堆AdjustUp(hp->a, hp->size-1)
}

删除：

顶部挪到最后一个 + 向下调整

void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1; //左孩子while (child < n){if (child + 1 < size && a[child] > a[child + 1]) //右孩子小于左孩子{++child;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

void HeapPop(Heap* hp) //删除
{assert(hp);assert(!HeapEmpty());swap(&hp->a[hp->size - 1], &hp->a[0]);size--;//向下调整AdjustDown(h[->a, hp->size, 0]);
}

取堆顶元素：

HPDataType HeapTop(Heap* hp)
{assert(hp);assert(hp->a);return hp->a[0];
}

堆销毁：

void HeapDestroy(Heap* hp)
{assert(hp);free(hp->a);hp->size = hp->capacity = 0;
}

判断堆是否为空：

bool HeapEmpty(Heap* hp)
{assert(hp);return hp->size == 0;//为空就返回true
}

TopK问题：

void TestTopk()//topk问题,找出n个数中的前k个最大数
{int n = 10000;int* a = (int*)malloc(sizeof(int) * n);srand(time(0));for (size_t i = 0; i < n; ++i){a[i] = rand() % 1000000;//生成一百万以内的随机数}a[5] = 1000000 + 1;a[1231] = 1000000 + 2;a[531] = 1000000 + 3;a[5121] = 1000000 + 4;a[115] = 1000000 + 5;a[2335] = 1000000 + 6;a[9999] = 1000000 + 7;a[76] = 1000000 + 8;a[423] = 1000000 + 9;a[3144] = 1000000 + 10;PrintTopK(a, n, 10);
}void PrintTopK(int* a, int n, int k)
{//要找最大的k的元素 //1、创建一个k大小的小堆//2、用堆顶元素和其他的n-k个元素比较，如果有比堆顶元素大的 就替换//3、替换完之后进行向下调整Heap hp;HeapInit(&hp);for (int i = 0; i < k; i++){HeapPush(&hp, a[i]);}for (int i = k; i < n; i++){if (a[i] > HeapTop(&hp)){hp.a[0] = a[i];AdjustDown(hp.a, hp.size, 0);}}HeapPrint(&hp);HeapDestroy(&hp);}

数据结构手撕--【堆】

目录编辑定义结构体： 初始化： 插入数据： 删除： 取堆顶元素： 堆销毁： 判断堆是否为空： TopK问题： 堆其实是完全二叉树物理结构：二叉树的层序遍历&#xff08…...

编程日记 2025/6/3 17:23:44

MySQL基本命令--系统+用户+表

前言：在当今数据驱动的时代，关系型数据库依然是构建信息系统的中坚力量，而MySQL作为开源领域中最广泛使用的数据库管理系统之一，以其高性能、稳定性和易用性赢得了开发者和企业的青睐。无论是在小型博客系统中承担数据存储职责&am…...

编程日记 2025/5/31 19:17:20

4.23-4.26学习总结 HTML—CSS常见标签和样式

页部导航栏： flex样式： 表单标签： （25行是设置点击按钮） 表单项标签： 搜索表单区域： 底部版权区域： 总结：...

编程日记 2025/5/29 19:51:07

使用Django框架表单文章目录使用Django框架表单[toc]1.使用Form类构建表单2.表单字段与Widget控件 1.使用Form类构建表单【创建项目和应用】 PS C:\Users\ls> cd E:\Python\ PS E:\Python> django-admin.exe startproject FormSite PS E:\Python> cd .\FormSite\…...

编程日记 2025/5/25 11:30:22

OpenCV第6课图像处理之几何变换（缩放）

1.简述图像几何变换又称为图像空间变换，它将一幅图像中的坐标位置映射到另一幅图像中的新坐标位置。几何变换并不改变图像的像素值，只是在图像平面上进行像素的重新安排。根据OpenCV函数的不同，本节课将映射关系划分为缩放、翻转、仿射变换、透视等。 2.缩放 2.1 函数…...

编程日记 2025/6/3 15:19:50

Python AI图像生成方案指南

1. 简介 AI图像生成是当前最热门的AI应用领域之一，Python提供了多种工具和库来实现这一功能。本指南将介绍几种主流的AI图像生成方案及其Python实现方法。 2. 主流AI图像生成技术 2.1 生成对抗网络(GANs) 原理：由生成器和判别器组成的对抗系统特点&am…...

编程日记 2025/6/3 16:07:14

【C++】stack、queue和priority_queue的模拟实现

文章目录前言一. stack1.1 stack的介绍1.2 stack的使用1.3 stack的模拟实现二. queue2.1 queue的介绍2.2 queue的使用2.3 queue的模拟实现三. deque3.1 deque的原理介绍3.2 deque的缺陷3.3 为什么选择deque作为stack和queue的底层默认容器四. priority_queue（优…...

编程日记 2025/6/2 16:43:04

Jmeter数据库url开关设置+常用Beanshell

1、数据库url开关设置 （79 90） jdbc:mysql://test.lemonban.com:3306/future?allowMultiQueries-true&characterEncodingUTF-8 多条查询开关：allowMultiQueriestrue 字符集配置:characterEncodingUTF-8 2、用BeanShell提取Map中的方…...

编程日记 2025/6/4 17:26:52

NtripShare 2025第一季度主要技术进展

GNSS方面 1、开源GNSS接收机配置软件基础版本。 2、商业版本GNSS接收机配置软件，增加PPP、文件保存、前端解算（静态、RTK-Static），前端坐标转换。 3、GNSS接收机配置软件全面适配米尔T133i硬件方案。视觉检测方面 1、做出第…...

编程日记 2025/6/4 4:25:47

Linux系统编程之内存映射

概述内存映射是操作系统提供的一种机制，使得文件或设备的内容可以直接映射到进程的虚拟地址空间中。这意味着，我们可以像访问数组一样读写文件内容，而不需要显式地调用I/O函数进行数据传输。内存映射适用于多种应用场景，包括但不…...

编程日记 2025/5/30 4:14:43

一文详解Adobe Photoshop 2025安装教程

Adobe Photoshop下载安装和使用教程 Adobe Photoshop，简称“PS”，是由Adobe Systems开发和发行的图像处理软件。Photoshop主要处理以像素所构成的数字图像。使用其众多的编修与绘图工具，可以有效地进行图片编辑和创造工作&#xff0c…...

编程日记 2025/6/4 1:37:42

ShenNiusModularity项目源码学习（23：ShenNius.Admin.Mvc项目分析-8）

用户列表页面用于检索、新建、编辑、删除系统用户，同时设置用户角色。该页面对应的文件Index.cshtml位于ShenNius.Admin.Mvc项目的Areas\Sys\Views\User内，同目录下还有Modify.cshtml（新建、编辑用户）、SetRole.cshtml&#xff08…...

编程日记 2025/6/2 13:39:48

vue中 vue.config.js反向代理

新建一个node 服务 1 npm init -y //创建一个package.json 2.npm i express 3. 新建一个app.js 4.键入代码 const express require("express") const app express()app.get("/user",(req,res)>{res.send({"name":"good"…...

编程日记 2025/6/2 21:50:16

AIGC赋能智慧医疗：从影像诊断到个性化治疗的革命性突破

一、医疗AIGC技术架构 1.1 医疗场景技术挑战医疗环节行业痛点 AIGC解决方案影像诊断人工阅片效率低多模态病灶分割与分级系统病历管理结构化程度低语音转文本智能编码药物研发周期长成本高分子生成与虚拟筛选个性化治疗方案标准化不足基因组学临床数据融合模型 1…...

编程日记 2025/6/3 20:40:24

Yarn 安装与使用教程

Yarn 安装与使用教程 Yarn 是一个由 Facebook 开发的 JavaScript 包管理工具，它比传统的 npm 更加高效、可靠，并且在性能上有所提升。Yarn 主要解决了 npm 安装速度慢、并发性差、缓存机制不完善等问题，它提供了更快的安装速度、更稳定的依赖…...

编程日记 2025/5/29 4:42:54

机器学习之二：指导式学习

正如人们有各种各样的学习方法一样，机器学习也有多种学习方法。若按学习时所用的方法进行分类，则机器学习可分为机械式学习、指导式学习、示例学习、类比学习、解释学习等。这是温斯顿在1977年提出的一种分类方法。有关机器学习的基本概念，…...

编程日记 2025/6/1 14:56:55

【学习笔记】检索增强生成（RAG）技术

检索增强生成（RAG）技术：原理、实现与发展趋势 1. RAG技术概述检索增强生成（Retrieval-Augmented Generation，RAG）是一种将信息检索与生成模型相结合的技术，旨在增强大型语言模型的知识能力和…...

编程日记 2025/6/2 8:50:57

计算机视觉——对比YOLOv12、YOLOv11、和基于Darknet的YOLOv7的微调对比

概述目标检测领域取得了巨大进步，其中 YOLOv12、YOLOv11 和基于 Darknet 的 YOLOv7 在实时检测方面表现出色。尽管这些模型在通用目标检测数据集上表现卓越，但在 HRSC2016-MS（高分辨率舰船数据集） 上对 YOLOv12 进行微调时&…...

编程日记 2025/6/4 4:45:24

Pygame跨平台打包：将游戏发布到Windows、Mac和Linux

Pygame跨平台打包：将游戏发布到Windows、Mac和Linux 引言在游戏开发的世界中，Pygame 是一个非常受欢迎的库，它使得使用 Python 编写 2D 游戏变得简单而有趣。然而，当你完成了一个游戏并希望将其发布给更多的玩家时，如何将你的游戏打包成可以在不同操作系统上运行的可执…...

编程日记 2025/6/2 19:42:27

关于图论的知识

如果一个无向图有 $n\times (n-1)\div 2$ 条边，称为**完全图** 如果一个完全图任意两个点都可以互相到达，称为**连通图** 一个包含 $dfs$ 与 $bfs$ 的图的遍历程序程序可做到的： 1、每一行输出一个 **搜索树** 2、$dfs$ 与 $bfs$ 并存 c…...

编程日记 2025/5/30 6:54:11

365打卡第R3周: RNN-心脏病预测

🍨 本文为🔗365天深度学习训练营中的学习记录博客 🍖 原作者：K同学啊 🏡 我的环境： 语言环境：Python3.10 编译器：Jupyter Lab 深度学习环境：torch2.5.1 torchvision0…...

编程日记 2025/6/4 6:27:15

如何解决IDE项目启动报错 error:0308010C:digital envelope routines::unsupported 问题

如何解决IDE项目启动报错 error:0308010C:digital envelope routines::unsupported 问题在现代软件开发过程中，开发人员通常使用集成开发环境（IDE）如IntelliJ IDEA、Visual Studio Code（VSCode）等进行Node.js项目开发…...

编程日记 2025/6/3 21:52:57

嵌入式学习笔记 - HAL_xxx_MspInit(xxx)；函数

使用cubeMX生成的HAL库函数中，所有外设的初始化函数HAL_xxx_Init(&xxxHandle)中都存在有此调用函数，此调用函数其实是对各外设模块比如UART，I2C等的底层硬件初始化，包括UART时钟，以及UART用到的GPIO的工作模式以及…...

编程日记 2025/6/3 21:43:33

Dify框架面试内容整理-Dify框架

什么是Dify框架？ Dify框架是一个开源的AI应用开发平台，专注于帮助开发者和非技术人员快速构建、部署和管理基于大语言模型（如GPT系列、国产开源模型）的应用。 Dify框架的特点：...

编程日记 2025/5/18 8:55:23

计算机网络的五层结构（物理层、数据链路层、网络层、传输层、应用层）到底是什么？

文章目录五层结构1. 物理层（Physical Layer）2. 数据链路层（Data Link Layer）3. 网络层（Network Layer）4. 传输层（Transport Layer）5. 应用层（Application Layer&#xf…...

编程日记 2025/5/29 4:42:59

【计算机视觉】CV实战项目 -深度解析PaddleSegSharp：基于PaddleSeg的.NET图像分割解决方案

深度解析PaddleSegSharp：基于PaddleSeg的.NET图像分割解决方案技术背景与项目概述核心功能与特点实战部署指南环境要求硬件要求软件依赖项目结构快速开始1. 获取项目2. 准备模型文件3. 运行示例高级使用技巧模型切换背景替换性能优化常见问题与解决方案技术原理…...

编程日记 2025/6/1 20:57:14

面试新收获-大模型学习

大模型原理 Transformer 架构与自注意力机制 Transformer 是当前大多数大模型采用的核心架构，由编码器-解码器组成，摒弃了传统 RNN 的顺序处理方式。Transformer 中关键在于多头自注意力机制（Multi-Head Self-Attention）&#xf…...

编程日记 2025/5/29 14:15:00

《Keras 3部署全攻略：从新手到实战高手》

《Keras 3部署全攻略：从新手到实战高手》一、引言：开启 Keras 3 部署之旅在深度学习的广阔领域中，Keras 一直以其简洁易用、高度模块化的特性，深受开发者的喜爱，被誉为深度学习的 “福音”。而如今，Keras 3 的强势登场，更是为这个领域注入了全新的活力。它像是一位集…...

编程日记 2025/5/29 16:23:15

如何修改npm的全局安装路径？

修改 npm 的全局安装路径可以通过以下步骤完成，确保全局包（使用 -g 安装的模块）和缓存文件存储到自定义路径。以下是详细步骤： 1. 创建自定义路径的目录在目标路径下创建两个文件夹，分别用于存储全局模块和缓存文件…...

编程日记 2025/5/30 16:40:26

计算机网络 | Chapter1 计算机网络和因特网

💓个人主页：mooridy-CSDN博客 💓文章专栏：《计算机网络：自定向下方法》大纲式阅读笔记_mooridy的博客-CSDN博客 🌹关注我，和我一起学习更多计算机网络的知识 🔝🔝 目录 …...

编程日记 2025/6/4 18:02:23

前端面试 HTML篇

src和href的区别 src和href都是用来加载外部资源，区别如下 src：当浏览器解析到该元素时，会暂停其他资源的加载和处理，直到该资源加载完成。它会将资源内容嵌入到当前标签所在的位置，将其指向的资源下载应用到文档内…...

编程日记 2025/6/2 23:37:50

Prometheus、Zabbix 和 Nagios 这三个工具的对100个节点的部署设计的信息流

Prometheus 1. 基本组件及角色 Prometheus主要由Prometheus Server、Exporter、Alertmanager和Grafana（可选）等组件构成。 Prometheus Server：负责数据的收集、存储和查询，以及规则的评估。Exporter：部署在被监控节点上，负责收集节点的各种指标数据。Alertmanager：负责…...

编程日记 2025/6/1 8:30:05

Tableau 基础表制作

目录 1.数据连接 2. 数据可视化 3. 基础表制作 3.1 对比分析：比大小 1. 柱状图 2. 条形图 3. 热力图 4. 气泡图 5. 词云 3.2 变化分析：看趋势 1. 折线图 2. 面积图 3.3 构成分析：看占比 1. 饼图 2. 树地图 3. 堆积图 3.4 关…...

编程日记 2025/6/2 10:41:04

openAICEO山姆奥特曼未来预测雄文之三个观察

《三个观察》山姆奥特曼这篇文章主要讲的是关于AGI（人工通用智能）的未来发展及其对社会的影响，用大白话总结如下： 核心观点： AGI是什么？ AGI是一种能像人类一样解决各种复杂问题的智能系统，比…...

编程日记 2025/6/1 11:07:42

springboot入门-service层构造器注入原理

在 Spring Boot 中，通过构造器注入的方式将 Repository（JPA）或 Mapper（MyBatis）注入到 Service 层的原理及示例如下： 1. 构造器注入的原理依赖注入（DI）机制： Spring 容…...

编程日记 2025/6/2 21:16:09

JavaScript 笔记 --- part6 --- JS进阶 (part1)

JS 进阶(part1) 作用域局部作用域定义: 局部作用域指的是在函数内部定义的变量，只能在函数内部访问，外部不能访问。特点: 局部作用域变量只能在函数内部或代码块中访问，外部不能访问。分类: 函数作用域: 指的是在函数内部定义的变量&…...

编程日记 2025/5/29 10:37:51

使用matplotlib绘制Raincloud图/云雨图/柱状图/小提琴图

需求： 使用Python的matplotlib绘制数据分布、数据箱型图、数据散点图参考： https://blog.csdn.net/weixin_39559994/article/details/128197965?fromshareblogdetail&sharetypeblogdetail&sharerId128197965&sharereferPC&sharesource…...

编程日记 2025/6/2 1:23:48

BT152-ASEMI机器人率器件专用BT152

编辑：LL BT152-ASEMI机器人率器件专用BT152 型号：BT152 品牌：ASEMI 封装：TO-220F 批号：最新引脚数量：3 封装尺寸：如图特性：单向可控硅工作结温：-40℃~150℃ …...

编程日记 2025/6/3 5:39:36

【Redis——通用命令】

文章目录 Redis为什么快？生产环境的概念Redis中最核心的两个命令get：通过key拿valueset：将key和value存入数据库其他通用命令keysexist判定key是否存在delexpire：为指定的key设置一个过期时间TTL（Time To Live&#x…...

编程日记 2025/5/29 12:57:49

qt之开发大恒usb3.0相机一

1.在大恒相机给的sample里没有看见qt开发的demo. 第一步先运行c sdk中中的demo，看了下代码，大恒使用的UI框架是MFC.然后 vs2022编译。运行结果第一步，先用qt进行坐下页面布局，如下图（保存图片的地方做了些更改&#…...

编程日记 2025/5/29 4:43:05

系列位置效应——AI与思维模型【80】

一、定义系列位置效应思维模型是指在一系列事物或信息的呈现过程中，人们对于处于系列开头和结尾部分的项目的记忆效果优于中间部分项目的现象。具体而言，开头部分的记忆优势被称为首因效应，结尾部分的记忆优势被称为近因效应。这种效应反映…...

编程日记 2025/6/3 1:27:32

解决conda虚拟环境安装包却依旧安装到base环境下

最近跑项目装包装到几度崩溃，包一直没有安装到正确位置，为此写下这篇文章记录一下，也希望能帮到有需要的人。（此文章开发环境为anaconda和window） 方法一先conda deactivate,看到（base）消失…...

编程日记 2025/6/3 13:26:48

设计看似完美却测不过？ Intra-Pair Skew 是「讯号完整性（Signal Integrity）」里最隐形的杀手

各位不知道有没有遇过，一对很长的差分走线，看起来很正常，但是测试结果偶尔会fail偶尔会pass，不像是软件问题，也不像是制程问题。看了一下Layout，发现阻抗匹配控制的非常好，TDR测试也显示阻抗好…...

编程日记 2025/5/31 4:27:25

使用MyBatis注解方式的完整示例，涵盖CRUD、动态SQL、分页、事务管理等场景，并附详细注释和对比表格

以下是使用MyBatis注解方式的完整示例，涵盖CRUD、动态SQL、分页、事务管理等场景，并附详细注释和对比表格： 项目结构 mybatis-annotation-demo/ ├── src/ │ ├── main/ │ │ ├── java/ │ │ │ └── com.example/…...

编程日记 2025/5/30 18:42:51

【头脑风暴】加权平均

一些加权平均而不是算术平均的思路，启发来源：ACLS,WACLS。简单平均假设所有样本的误差和噪声特性相同，但在实际电路中，不同阶段、不同时间点的样本价值（对最终精度的贡献）是不同的。加权平均的核心思想…...

编程日记 2025/5/30 23:48:37

DAM-3B，英伟达推出的多模态大语言模型

DAM-3B是什么 DAM-3B（Describe Anything 3B）是英伟达推出的一款多模态大语言模型，专门用于为图像和视频中的特定区域生成详细描述。用户可以通过点、边界框、涂鸦或掩码等方式来标识目标区域，从而得到精准且符合上下文的文本描述…...

编程日记 2025/5/29 4:42:56

2025年暨南大学 ACM校赛分析与题解

文章目录 C.最长公共前缀D.排列H.回文串法不定法，在于因时因势AC不了就是还得加练！ C.最长公共前缀字典树模版题目，不了解字典树的同学，可以看我的另一篇博客算法之字典树 class Node: # 和模版题目相似，但是多…...

编程日记 2025/5/30 22:19:08

图像处理——边缘检测

1 概述边缘检测是图像处理和计算机视觉中的一项基本技术，用于识别图像中亮度变化剧烈的像素点，这些像素点通常对应于物体的边界。它通过检测图像中亮度或颜色变化显著的区域，提取出物体的轮廓，常用于计算机视觉、图像处理和模式识…...

编程日记 2025/5/29 17:05:28

认识哈希以及哈希表的模拟实现

文章目录 1.什么是哈希2.哈希函数2.1 除留余数法/除法散列法2.2 乘法散列法2.3 全域散列法 3.哈希冲突4.解决哈希冲突的方法4.1 开放定址法4.1.1 用除留余数法和线性探测模拟实现简单的哈希表 4.2 链地址法4.2.1 用除留余数法和链地址法模拟实现简单的哈希表 1.什么是哈希概念…...

编程日记 2025/6/2 21:11:09

【Castle-X机器人】二、智能导览模块安装与调试

持续更新。。。。。。。。。。。。。。。【Castle-X机器人】智能导览模块安装与调试二、智能导览模块安装与调试2.1 智能导览模块安装2.2 智能导览模块调试2.2.1 红外测温传感器测试2.2.2 2D摄像头测试二、智能导览模块安装与调试 2.1 智能导览模块安装使用相应工具将智能…...

编程日记 2025/6/3 20:09:26

定义结构体：

初始化：

插入数据：

删除：

取堆顶元素：

堆销毁：

判断堆是否为空：

TopK问题：

相关文章：