[数据结构]7. 堆-Heap
堆-Heap
- 1. 介绍
- 2. 堆的实现
- 3. 堆操作
- Initlilze
- Destory
- Swap
- Push
- Pop
- Top
- Empty
- Size
- AdjustUp
- AdjustDown
- 4. HeapSort
- 5. Top-K
1. 介绍
堆(heap) 是一种满足特定条件的完全二叉树。
- 小顶堆(min heap):任意节点的值 ≤ 其子节点的值。
- 大顶堆(max heap):任意节点的值 ≥ 其子节点的值
堆作为完全二叉树的一个特例,具有以下特性。
- 最底层节点靠左填充,其他层的节点都被填满。
- 将根节点称为“堆顶”,将底层最靠右的节点称为“堆底”。
- 大顶堆,根节点值是最大的。
- 小顶堆,根节点值是最小的。
2. 堆的实现
完全二叉树非常适合用数组来表示。
使用数组表示二叉树时,元素代表节点值,索引代表节点在二叉树中的位置。
节点指针通过索引映射公式来实现:
给定索引 𝑖 ,其左子节点的索引为 2𝑖 + 1 ,右子节点的索引为 2𝑖 + 2 ,父节点的索引为(𝑖 - 1)/2(向下整除)。当索引越界时,表示空节点或节点不存在。
3. 堆操作
Initlilze
void HeapInit(HP* php) {assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}
Destory
void HeapDestory(HP* php) {assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}
Swap
void Swap(HPDataType* p1, HPDataType* p2) {HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
Push
void HeapPush(HP* php, HPDataType x) {assert(php);if (php->size == php->capacity) {int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//向上排序
}
Pop
void HeapPop(HP* php) {assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}
Top
HPDataType HeapTop(HP* php) {assert(php);assert(!HeapEmpty(php));return php->a[0];
}
Empty
bool HeapEmpty(HP* php) {assert(php);return php->size == 0;
}
Size
int HeapSize(HP* php) {assert(php);return php->size;
}
AdjustUp
void AdjustUp(HPDataType* a, int child) {int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]) {// 小堆Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}
AdjustDown
void AdjustDown(HPDataType* a, int n, int parent) {// n为数据个数int child = parent * 2 + 1;while (child < n) {if (child + 1 < n && a[child] > a[child + 1]) {child++;}if (a[child] > a[parent]) {// maxSwap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}
4. HeapSort
void HeapSort(int* a, int n) {// 升序--建大堆 max// 建堆--向下调整堆--O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i) {AdjustDown(a, n, i);}int end = n - 1;while (end > 0) {Swap(&a[0], &a[end]);// 把堆顶max放在最后// 再调整,选出次小的,升序AdjustDown(a, end, 0);--end;}
}
5. Top-K
给定一个长度为 𝑛 的无序数组 nums ,请返回数组中最大的 𝑘 个元素。
Top‑k 是一个经典算法问题,可以使用堆数据结构高效解决,时间复杂度为 𝑂(𝑛 log 𝑘)
方案:
- 初始化一个小顶堆,其堆顶元素最小。
- 先将数组的前 𝑘 个元素依次入堆。
- 从第 𝑘 + 1 个元素开始,若当前元素大于堆顶元素,则将堆顶元素出堆,并将当前元素入堆。
- 遍历完成后,堆中保存的就是最大的 𝑘 个元素。
void CreateNData() {int n = 1000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");for (size_t i = 0; i < n; i++) {int x = rand() % 10000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void PrintTopK(int k) {const char* file = "data.txt";FILE* fout = fopen(file, "r");int* kminheap = (int*)malloc(sizeof(int) * k);for (int i = 0; i < k; i++) {fscanf(fout, "%d", &kminheap[i]);}for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, k, i);}int val = 0;while (!feof(fout)) {//未到达文件末尾,feof返回零。fscanf(fout, "%d", &val);if (val > kminheap[0]) {kminheap[0] = val;AdjustDown(kminheap, k, 0);}}for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}
相关文章:
[数据结构]7. 堆-Heap
堆-Heap 1. 介绍2. 堆的实现3. 堆操作InitlilzeDestorySwapPushPopTopEmptySizeAdjustUpAdjustDown 4. HeapSort5. Top-K 1. 介绍 堆(heap) 是一种满足特定条件的完全二叉树。 小顶堆(min heap):任意节点的值 ≤ 其子…...
对心理幸福感含义的探索 | 幸福就是一切吗?
注:机翻,未校。 Happiness Is Everything, or Is It? Explorations on the Meaning of Psychological Well-Being 幸福就是一切吗?对心理幸福感含义的探索 Journal of Personality and Social Psychology 1989, Vol. 57, No. 6,1069-1081 …...
Java应用OOM排查:面试通关“三部曲”心法
开篇点题:OOM——Java应用的“内存爆仓”警报 OOM (OutOfMemoryError) 是啥病?想象一下,你的Java应用程序是一个大仓库,内存就是仓库的存储空间。如果货物(程序运行时创建的对象)越来越多,超出了…...
第28周——InceptionV1实现猴痘识别
前言 🍨 本文为🔗365天深度学习训练营中的学习记录博客🍖 原作者:K同学啊 一、前期准备 1.检查GPU import torch import torch.nn as nn import torchvision.transforms as transforms import torchvision from torchvision im…...
云上玩转 Qwen3 系列之三:PAI-LangStudio x Hologres构建ChatBI数据分析Agent应用
本文详细介绍了如何使用 LangStudio 和 Qwen3 构建基于 MCP 协议的 Hologres ChatBI 智能 Agent 应用。该应用通过将 Agent、MCP Server 等技术和阿里最新的推理模型 Qwen3 编排在一个应用流中,为大模型提供了 MCPOLAP 的智能数据分析能力,使用自然语言即…...
Android开发-在应用之间共享数据
在Android系统中,应用之间的隔离机制(沙箱机制)保障了系统的安全性与稳定性。然而,在实际开发中,我们经常需要实现跨应用的数据共享,例如: 从一个应用向另一个应用传递用户信息;多个…...
MySQL-数据库分布式XA事务
准备 innodb存储引擎开启支持分布式事务 set global innodb_support_axonMySQL数据库XA事务的SQL语法如下: XA {START| BEGIN} xid {JOIN | RESUME} XA END xid {SUSPEND [ FOR MIGRATE]} XA PREPARE xid XA COMMIT xid [ONE PHASE] XA ROLLBACK xid XA RECOVER 完…...
如何快速入门-衡石科技分析平台
快速指南 创建管理员账号 按照文档安装成功之后,假设安装所在服务器 IP 是<Server IP>,端口是<Server Port>,则可以通过浏览器访问http://<Server IP>:<Server Port>/ 访问衡石分析平台,如果正常&a…...
20250515通过以太网让VLC拉取视熙科技的机芯的rtsp视频流的步骤
20250515通过以太网让VLC拉取视熙科技的机芯的rtsp视频流的步骤 2025/5/15 20:26 缘起:荣品的PRO-RK3566适配视熙科技 的4800W的机芯。 1080p出图预览的时候没图了。 通过105的机芯出图确认 荣品的PRO-RK3566 的硬件正常。 然后要确认 视熙科技 的4800W的机芯是否出…...
OpenCV CUDA模块中矩阵操作-----矩阵最大最小值查找函数
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在OpenCV的CUDA模块中,矩阵最大最小值查找操作用于快速获取矩阵中的全局最小值、最大值及其位置。这些函数对于图像处理任务特别有用…...
OpenCv高阶(4.0)——案例:海报的透视变换
文章目录 前言一、工具函数模块1.1 图像显示函数1.2 保持宽高比的缩放函数1.3 坐标点排序函数 二、透视变换核心模块2.1 四点透视变换实现 三、主流程技术分解3.1 图像预处理3.2 轮廓检测流程3.3 最大轮廓处理 四、后处理技术4.1 透视变换4.2 形态学处理 五、完整代码总结 前言…...
JavaScriptWeb API (DOM和BOM操作)
Web API (基础部分) 作用: 使用 JS 去操作 html 和浏览器 分类: DOM 和 BOM DOM: 操作 HTML 文档的 APIBOM: 操作浏览器的 API DOM(文档对象模型) 是用来呈现以及与任意 HTML 或 XML 文档进行交互的 API 作用: 开发网页内容特效和实现用户交互 动态创建 HTML 元素改变 HTML…...
AM-Thinking-v1论文解读:以32B规模推进推理前沿
《AM-Thinking-v1: Advancing the Frontier of Reasoning at 32B Scale》论文解读 一、引言 过去半年,大型语言模型(LLMs)在推理领域(如数学问题求解和代码生成)取得了显著进展,扩大了其在现实场景中的应…...
Spark--RDD中的转换算子
1、算子的简单介绍 Transformation(转换)算子:根据数据集创建一个新的数据集,计算后返回一个新RDD,例如一个rdd进行map操作后生了一个新的rdd。 Action(动作)算子:对rdd结果计算后返回一个数值value给驱动程序(driver),例如collect算子将数据集的所有元素收集完成返回给驱动程…...
【文件上传漏洞】
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文件上传漏洞 定义客户端js检测 服务器检测后缀黑名单白名单 检测内容其他 定义 文件上传漏洞是指用户上传了一个可执行的脚本文件,并通过此脚本文件获得了执行服…...
electron进程通信
electron进程通信 模式 1:渲染器进程到主进程(单向) send和on 1.渲染器进程调用方法 click setTitle2.预加载进程暴露setTile方法 setTitle: (title) > ipcRenderer.send(set-title, title),3.主进程监听到方法 ipcMain.on(set-title…...
[C++面试] lambda面试点
一、入门 1、什么是 C lambda 表达式?它的基本语法是什么? Lambda 是 C11 引入的匿名函数对象,用于创建轻量级的可调用对象。 [捕获列表] (参数列表) mutable(可选) 异常声明(可选) -> 返回…...
【愚公系列】《Manus极简入门》040-科技与组织升级顾问:“项目掌舵人”
🌟【技术大咖愚公搬代码:全栈专家的成长之路,你关注的宝藏博主在这里!】🌟 📣开发者圈持续输出高质量干货的"愚公精神"践行者——全网百万开发者都在追更的顶级技术博主! …...
2505C++,py和go调用雅兰亭库的协程工具
原文 神算调用C 一般调用pybind11封装的C库实现神算调用C库,pybind11封装c的接口很简单. 创建一个py_example.cpp文件 #include <pybind11/pybind11.h> #include <string> namespace py pybind11; PYBIND11_MODULE(py_example, m) {m.def("hello", …...
题解:P12207 [蓝桥杯 2023 国 Python B] 划分
链接 题目描述 给定 40 个数,请将其任意划分成两组,每组至少一个元素。每组的权值为组内所有元素的和。划分的权值为两组权值的乘积。请问对于以下 40 个数,划分的权值最大为多少。 5160 9191 6410 4657 7492 1531 8854 1253 4520 9231126…...
英迈国际Ingram Micro EDI需求分析
Ingram Micro(英迈国际)成立于1979年,是全球领先的技术和供应链服务提供商,总部位于美国加州尔湾。公司致力于连接全球的技术制造商与渠道合作伙伴,业务涵盖IT分销、云服务、物流和供应链优化等多个领域。Ingram Micro…...
【Linux】网络基础与socket编程基础
一.网络发展 计算机的出现是在网络之前的。而网络产生之初就是为了解决局部计算机无法交互的问题。所以,网络在诞生之初,最先出现的就是我们的局域网LAN,用来结局局部多台计算机的通信问题。 而随着时间的推移,局域网已经不能满…...
漂亮的收款打赏要饭网HTML页面源码
这是一款专为个人收款及接受打赏设计的HTML页面,其设计简洁且美观。 下载地址:漂亮的收款打赏要饭网HTML页面源码 备用地址:漂亮的收款打赏要饭网HTML页面源码...
【图书推荐】几本人工智能实用性图书
《OpenCV计算机视觉开发实践:基于Python》 《OpenCV计算机视觉开发实践:基于Python》【摘要 书评 试读】- 京东图书 《PyTorch深度学习与计算机视觉实践》 《PyTorch深度学习与计算机视觉实践(人工智能技术丛书)》(王晓华)【摘要 书评 试读…...
uniapp+vite+cli模板引入tailwindcss
目前vitecli方式用的都是官方提供的模板,vite版本还是4.14版本,较旧,而tailwindcss已经有了4版本,实际发现引入最新版会报错,因而继续使用3.3.5版本 pnpm install tailwindcss3.3.5 uni-helper/vite-plugin-uni-tail…...
【使用 C# 获取 USB 设备信息及进行通信】
文章目录 使用 C\# 获取 USB 设备信息及进行通信为什么需要获取 USB 设备信息?方法一:使用 C\# 库 (推荐)1. HidSharp2. LibUsbDotNet 方法二:直接调用 Windows API (P/Invoke)理解设备通信协议 (用于数据交换)总结 使用 C# 获取 USB 设备信息…...
Spring Cloud探索之旅:从零搭建微服务雏形 (Eureka, LoadBalancer 与 OpenFeign实战)
引言 大家好!近期,我踏上了一段深入学习Spring Cloud构建微服务应用的旅程。我从项目初始化开始,逐步搭建了一个具备服务注册与发现、客户端负载均衡以及声明式服务调用功能的基础微服务系统。本文旨在记录这一阶段的核心学习内容与实践成果…...
四维时空数据安全传输新框架:压缩感知与几何驱动跳频
四维时空数据安全传输新框架:压缩感知与几何驱动跳频 1. 引言 1.1 研究背景 随着三维感知技术(如激光雷达、超宽带定位)与动态数据流(如无人机集群、工业物联网)的快速发展,四维时空数据(三维…...
CSS相关知识补充
:root伪类 css自定义变量和var()引用自定义变量 https://developer.mozilla.org/zh-CN/docs/Web/CSS/var 在 SCSS 中,变量的声明和使用是用 $ 符号,比如: $primary-color: #ff5722;.button {color: $primary-color; }SCSS 里没有 var() 这…...
DeepSeek 赋能物联网:从连接到智能的跨越之路
目录 一、引言:物联网新时代的开启二、DeepSeek 技术揭秘2.1 DeepSeek 是什么2.2 DeepSeek 技术优势 三、DeepSeek 与物联网的融合之基3.1 物联网发展现状与挑战3.2 DeepSeek 带来的变革性突破 四、DeepSeek 在物联网的多元应用场景4.1 智慧电力:开启能源…...
谷歌量子计算机:开启计算新纪元
量子计算的黎明 原始尺寸更换图片 在科技迅猛发展的时代,量子计算作为前沿领域,正逐渐崭露头角,吸引着全球无数科研人员与科技巨头的目光。它宛如一把开启未来科技大门的钥匙,为解决诸多复杂难题提供了前所未有的可…...
桃芯ingchips——windows HID键盘例程无法同时连接两个,但是安卓手机可以的问题
目录 环境 现象 原理及解决办法 环境 PC:windows11 安卓:Android14 例程使用的是HID Keyboard,板子使用的是91870CQ的开发板,DB870CC1A 现象 连接安卓手机时并不会出现该现象,两个开发板都可以当做键盘给手机发按…...
AMC8 -- 2009年真题解析(中文解析)
Problem 1 Answer: E 中文解析: Bridget最后有4个,给了Cassie3个, 则给Cassie之前有7个。在此之前给了一半的苹果给Ann, 那么在给Anna之前,他有7*214个苹果。 因此答案是E。 Problem 2 Answer: D 中文解析࿱…...
深入解析CountDownLatch的设计原理与实现机制
精心整理了最新的面试资料和简历模板,有需要的可以自行获取 点击前往百度网盘获取 点击前往夸克网盘获取 一、概述 CountDownLatch是Java并发包(java.util.concurrent)中用于协调多线程同步的核心工具类,其设计目标是允许一个或…...
缓存的相关内容
缓存是一种介于数据永久存储介质与数据应用之间数据临时的存储介质 实用化保存可以有效地减少低俗数据读取的次数 (例如磁盘IO), 提高系统性能 缓存不仅可以用于提高永久性存储介质的数据读取效率,还可以提供临时的数据存储空间 spring boot中提供了缓存技术, 方便…...
JVM方法区核心技术解析:从方法区到执行引擎
方法区 方法区的内部结构 在经典方法区设计中,主要存储以下核心数据内容: 一、类型信息 方法区维护的类型信息包含以下要素: 类全称标识 类名称(含完整包路径)直接父类的完全限定名(包含完整包路径&am…...
AIbase推出全球MCP Server集合平台 收录超12万个MCP服务器客户端
2025年,AI领域迎来了一项重要的技术进展——MCP(Model Context Protocol,模型上下文协议)的广泛应用。全球MCP Server集合平台AIbase(https://mcp.aibase.cn/)应运而生,为AI开发者提供了一站式的MCP服务器和客户端整合…...
Python训练打卡Day22
复习日: 1.标准化数据(聚类前通常需要标准化) scaler StandardScaler() X_scaled scaler.fit_transform(X) StandardScaler() :这部分代码调用了 StandardScaler 类的构造函数。在Python中,当你在类名后面加上括号…...
【ALINX 实战笔记】FPGA 大神 Adam Taylor 使用 ChipScope 调试 AMD Versal 设计
本篇文章来自 FPGA 大神、Ardiuvo & Hackster.IO 知名博主 Adam Taylor。在这里感谢 Adam Taylor 对 ALINX 产品的关注与使用。为了让文章更易阅读,我们在原文的基础上作了一些灵活的调整。原文链接已贴在文章底部,欢迎大家在评论区友好互动。 在上篇…...
【数据结构入门训练DAY-35】棋盘问题
本次训练聚焦于使用深度优先搜索(DFS)算法解决棋盘上的棋子摆放问题。题目要求在一个可能不规则的nn棋盘上摆放k个棋子,且任意两个棋子不能位于同一行或同一列。输入包括棋盘大小n和棋子数k,以及棋盘的形状(用#表示可放…...
张 提示词优化(相似计算模式)深度学习中的损失函数优化技巧
失函数的解释 损失函数代码解析 loss = -F.log_softmax(logits[...
Elasticsearch 常用语法手册
🧰 Elasticsearch 常用语法手册 📚 目录 索引操作文档操作查询操作聚合查询健康与状态查看常见问题与注意事项 🔹 索引操作 查询全部索引 GET _search创建索引 PUT /es_db创建索引并设置分片数和副本数 PUT /es_db {"settings&quo…...
华宇TAS应用中间件与亿信华辰多款软件产品完成兼容互认证
近日,华宇TAS应用中间件与亿信华辰多款产品成功通过兼容互认证测试,双方产品在功能协同、性能优化及高可用性等维度实现全面适配,将为用户提供更加稳定、高效、安全的国产化解决方案。 此次认证也标志着华宇在国产化生态适配领域再添重要里程…...
AI大模型从0到1记录学习numpy pandas day24
第 1 章 环境搭建 1.1 Anaconda 1.1.1 什么是Anaconda Anaconda官网地址:https://www.anaconda.com/ 简单来说,Anaconda Python 包和环境管理器(Conda) 常用库 集成工具。它适合那些需要快速搭建数据科学或机器学习开发环境的用…...
开源GPU架构RISC-V VCIX的深度学习潜力测试:从RTL仿真到MNIST实战
点击 “AladdinEdu,同学们用得起的【H卡】算力平台”,H卡级别算力,按量计费,灵活弹性,顶级配置,学生专属优惠。 一、开篇:AI芯片架构演变的三重挑战 (引述TPUv4采用RISC-V的行业案…...
VirtualiSurg使用SenseGlove触觉手套开发XR手术培训体验
虚拟现实和虚拟现实触觉 作为一个领先的培训平台,VirtualiSurg自2017年以来一直利用扩展现实(XR)和触觉技术,为全球医疗保健行业提供个性化的数据驱动学习解决方案。它们使医疗专业人员能够协作学习和培训,提高他们的技能,让他们…...
AbstractErrorController简介-笔记
1. AbstractErrorController简介 org.springframework.boot.autoconfigure.web.servlet.error.AbstractErrorController 是 Spring Boot 提供的一个用于处理 HTTP 错误(如 404、500 等)的抽象类,用于自定义错误响应的逻辑。它是 Spring Boot…...
next.js实现项目搭建
一、创建 Next.js 项目的步骤 1、安装 npx create-next-applatest # 或 yarn create next-app # 或 pnpm create next-app 按照交互式提示配置你的项目: 输入项目名称 选择是否使用 TypeScript 选择是否启用 ESLint 选择是否启用 Tailwind CSS 选择是否使用 s…...
使用GoLang版MySQLDiff对比表结构
概述 下载地址: https://github.com/camry/mysqldiff/ 编译安装 git clone https://github.com/camry/mysqldiff.git go env -w GOPROXYhttps://goproxy.cn,direct go env -w GOPRIVATE*.corp.example.com go build .\mysqldiff.go执行对比 ./mysqldiff --sourc…...
git工具使用详细教程-------命令行和图形化工具
下载 git下载地址:https://git-scm.com/downloads TortoiseGit(图形化工具)下载地址:https://tortoisegit.org/download/ 认识git结构 工作区:存放代码的地方 暂存区:临时存储,将工作区的代码…...