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

数据结构-堆的实现和应用

news 来源：原创 2025/7/16 12:13:07

1.堆的概念

2.堆的构建

3.堆的实现

4.堆的功能实现

4.1堆的初始化

4.2堆的销毁

4.3堆的插入

4.3.1向上调整

4.4堆的删除

4.4.1向下调整法

编辑4.5取堆顶

5. 向上调整法和向下调整法比较

6.堆的应用

6.1TOP-K问题

6.2TOP-K思路

6.2.1用前n个数据来建堆

6.2.2剩下的N-K

6.3示例

1.堆的概念

堆的底层是数组，所以堆也是一种特殊的数组。

堆分为大堆和小堆

大堆：父节点不小于子节点
小堆：父节点不大于子节点

2.堆的构建

已经提到堆是一种数组，那么要怎么实现呢。

先以小堆为例，已知父节点不小于子节点，使用数组，数组下标0是根节点，1和2是他的子节点，接着1的子节点是3和4,2的子节点是5和6，这样就可以实现一个堆了。

3.堆的实现

既然是数组，就要有指针，容量大小。

4.堆的功能实现

4.1堆的初始化

4.2堆的销毁

4.3堆的插入

一直到这一步，都是和栈是相同的，因为我们插入数据了，这时我们无法保证这是一个堆，所以此时要进行向上调整。

4.3.1向上调整

因为此时插入是数据再最下面，所以要和上面的进行比较调整。

4.4堆的删除

我们是删除堆的最后一个元素，要怎么删除呢，我们可以将最后一个元素和第一个元素进行交换，然后使堆向下调整即可。

4.4.1向下调整法

4.5取堆顶

5. 向上调整法和向下调整法比较

推导时间复杂度，由于用图来表示有些难度，这里直接用笔写出来

这是向下调整法的推导过程

向下调整建堆的时间复杂度如图

下面是向上调整建堆的时间复杂度推导

总结:向上调整算法建堆是优于向下调整建堆的。

6.堆的应用

6.1TOP-K问题

这种问题通常是在较大的数据样本中取出其中的最值，这时就可以通过堆来完成。

通常这类问题样本较大，排序就不太可取，可以建堆来实现。

6.2TOP-K思路

6.2.1用前n个数据来建堆

求最大的前n个就建小堆

求最小的前n个就建大堆

6.2.2剩下的N-K

用剩下的N-K个数据来和堆顶数据比较，不满足就替换堆顶元素

6.3示例

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
#include<time.h>
void test()
{HP hp;HPInit(&hp);HPPush(&hp, 2);HPPush(&hp, 4);HPPush(&hp, 1);HPPush(&hp, 1); printf("%d", HPTop(&hp));}
void CreateNDate()
{int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (file == NULL){perror("fopen fail");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void topk()
{int k = 0;printf("输入k的值\n");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");int* arr = (int*)malloc(sizeof(int) * k);for (int i = 0; i < k; i++){fscanf(fout, "%d", &arr[i]);}//建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, k);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > arr[0]){arr[0] = x;AdjustDown(arr, 0, k);}}for (int i = 0; i < k; i++) {printf("%d ", arr[i]);}fclose(fout);
}int main()
{CreateNDate();topk();return 0;
}

数据结构-堆的实现和应用

目录 1.堆的概念 2.堆的构建 3.堆的实现 4.堆的功能实现 4.1堆的初始化 4.2堆的销毁 4.3堆的插入 4.3.1向上调整 4.4堆的删除 4.4.1向下调整法编辑4.5取堆顶 5. 向上调整法和向下调整法比较 6.堆的应用 6.1TOP-K问题 6.2TOP-K思路 6.2.1用前n个数据来建堆 6.…...

编程日记 2025/7/16 12:13:07

Spring MVC

1. 用户发起请求用户行为：用户在浏览器中输入URL或点击链接，向Web服务器（如Tomcat）发起一个HTTP请求。请求传输：请求被发送到Web容器，Web容器根据配置将请求转发给DispatcherServlet。 2. 前端控制器&am…...

编程日记 2025/7/17 10:44:21

linux ubuntu的脚本知

目录一、变量的引用二、判断指定的文件是否存在三、判断目录是否存在四、判断最近一次命令执行是否成功五、一些比较符号六、"文件"的读取和写入七、echo打印输出八、ubuntu切换到root用户九、后台进程的控制 N、其它可以参考的网址脚本功能强大…...

编程日记 2025/7/12 12:47:52

Spring Boot 动态数据源切换

背景随着互联网应用的快速发展，多数据源的需求日益增多。Spring Boot 以其简洁的配置和强大的功能，成为实现动态数据源切换的理想选择。本文将通过具体的配置和代码示例，详细介绍如何在 Spring Boot 应用中实现动态数据源切换，帮…...

编程日记 2025/7/13 2:38:24

Design Linear Filters in the Frequency Domain (MATLAB帮助文档)

Design Linear Filters in the Frequency Domain 这个帮助文档写得很好，简单明了，一句废话没有。 This topic describes functions that perform filtering in the frequency domain. 2-D Finite Impulse Response (FIR) Filters The Image Processi…...

编程日记 2025/7/17 10:49:51

Java知识及热点面试题总结（二）

1、什么是死锁(deadlock)? 两个线程或两个以上线程都在等待对方执行完毕才能继续往下执行的时候就发生了死锁。结果就是这些线程都陷入了无限的等待中。如何避免线程死锁? 只要破坏产生死锁的四个条件中的其中一个就可以了。破坏互斥条件：这个条件我们没有办法…...

编程日记 2025/7/14 20:52:35

开源加密库mbedtls及其Windows编译库

目录 1 项目简介 2 功能特性 3 性能优势 4 平台兼容性 5 应用场景 6 特点 7 Windows编译 8 编译静态库及其测试示例下载 1 项目简介 Mbed TLS是一个由ARM Maintained的开源项目，它提供了一个轻量级的加密库，适用于嵌入式系统和物联网设备。这个项…...

编程日记 2025/7/16 5:29:31

架构01-演进中的架构

零、文章目录架构01-演进中的架构 1、原始分布式时代：Unix设计哲学下的服务探索 （1）背景时间：20世纪70年代末到80年代初计算机硬件：16位寻址能力、不足5MHz时钟频率的处理器、128KB左右的内存转型：从…...

编程日记 2025/7/16 20:32:49

npm-运行项目报错：A complete log of this run can be found .......npm-cache_logs\

1.问题没有找到对应的某种依赖，node_modules出现问题。 2.解决 (1)查看对应依赖是否引入或者是由于合并分支错误引入js或依赖不存在。谨慎删除依赖包 (2)查找对应引入依赖进行安装最后解决方法-删除依赖包清除缓存 npm cache clean --force (2)重新向同事引入…...

编程日记 2025/7/5 4:50:57

C++中的函数对象

C 中函数对象的定义和特点定义：函数对象（Function Object）也叫仿函数（Functor），是一个类，这个类重载了函数调用运算符()。当创建这个类的对象后，可以像使用函数一样使用这个对象&am…...

编程日记 2025/7/15 13:12:29

godot游戏引擎_瓦片集和瓦片地图介绍

在 Godot 中，TileSet 和 TileMap 是用于处理瓦片地图的两个关键概念，它们的作用和用途有明显的区别。以下是两者的详细对比： 1. TileSet（瓦片集） TileSet 是资源，定义瓦片的内容和属性。特点&#xff1a…...

编程日记 2025/7/14 13:19:50

[C++ 核心编程]笔记 4.1 封装

4.1.1 封装的意义封装是C面向对象三大特性之一封装的意义: 将属性和行为作为一个整体，表现生活中的事物将属性和行为加以权限控制封装意义一: 在设计类的时候，属性和行为写在一起，表现事物语法: class 类名{ 访问权限: 属性 /行为 }…...

编程日记 2025/7/14 21:23:51

学习使用jquery实现在指定div前面增加内容

学习使用jquery实现在指定div前面增加内容设计思路代码示例设计思路选择要添加内容的指定元素‌： 使用jQuery选择器来选择你希望在其前添加内容的元素。例如，如果你有一个元素，其ID为qipa250，你可以使用$(‘#qipa250’)来选择…...

编程日记 2025/7/12 23:32:02

如何写出好证明（支持思想的深入数学写作）

不断的修改和精炼是写作过程中的重要环节，数学写作最终目的是提供对问题的深刻洞察而非仅仅陈述细节。根据harvey mudd college Francis Su教授的《GUIDELINES FOR GOOD MATHEMATICAL WRITING》讲稿，总结出撰写好的数学证明需要注意以下几个要点&#x…...

编程日记 2025/7/16 8:34:27

基于边缘智能网关的机房安全监测应用

随着我国工业互联网的扎实推进，越来越多地区积极建设信息基础设施，以充沛算力支撑产业物联网的可持续发展，数据机房就是其中的典型代表。而且随着机房规模的扩大，对于机房的安全管理难题挑战也日益增加。面向数据机房安全监测与管…...

编程日记 2025/7/15 23:28:09

在WSL 2 (Ubuntu 22.04)安装Docker Ce 启动错误解决

查看WSL版本在 Windows 命令提示符（CMD）或 PowerShell 中，你可以使用以下命令来查看已安装的 WSL 发行版及其版本信息： wsl -l -v(base) PS C:\Users\Lenovo> wsl -l -vNAME STATE VERSION * Ubuntu-2…...

编程日记 2025/7/14 20:24:10

【RISC-V CPU debug 专栏 3 -- Debugging RISC-V Cores】

文章目录 RISC-V 调试规范开源与多样性挑战调试规范的重要性外部调试支持的主要组件调试功能Lauterbach 的贡献RISC-V 调试规范调试 RISC-V 内核涉及许多独特的挑战，这是由 RISC-V 的开源特性和多样化的生态系统所决定的。为了避免专有调试接口的泛滥，RISC-V 基金会内的工作…...

编程日记 2025/7/16 1:33:57

Unity Banner广告后面自定义背景，高度适配

目的是实现这个，代码放下面已经测试十几台设备包括pad没问题以Max聚合为例展示（关闭）Banner的时候调用Show，Banner加载成功回调里调用RefreshSizeDelta 最终获得是像素所以UGUI的Canvas使用Constant Pixel Size模式&#xff0…...

编程日记 2025/7/13 11:25:55

【技术文档：技术传播的灯塔】

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。推荐:kwan 的首页,持续学…...

编程日记 2025/7/13 19:00:06

git的使用（简洁版）

什么是 Git？ Git 是一个分布式版本控制系统 (DVCS)，用于跟踪文件的更改并协调多人之间的工作。它由 Linus Torvalds 在 2005 年创建，最初是为了管理 Linux 内核的开发。Git 的主要目标是提供高效、易用的版本控制工具，使得开发者…...

编程日记 2025/7/13 20:46:22

数据库编程（sqlite3）

一：数据库分类常用的数据库大型数据库 ：Oracle商业、多平台、关系型数据库功能最强大、最复杂、市场占比最高的商业数据库中型数据库 ：Server是微软开发的数据库产品，主要支持windows平台小型数据库 : mySQL是一个小型关系型…...

编程日记 2025/7/12 15:11:01

Python 中如何处理异常？

在Python中，异常处理是一种重要的编程技术，它允许开发者优雅地处理程序运行过程中出现的错误或异常情况，而不是让程序直接崩溃。通过异常处理，我们可以使程序更加健壮、用户友好。异常处理的基本结构 Python中最基本的异常处…...

编程日记 2025/7/14 10:49:15

RHCE——nfs网络文件系统

简介 NFS（Network File System，网络文件系统）是FreeBSD支持的文件系统中的一种，它允许网络中的计算机（不同的计算机、不同的操作系统）之间通过TCP/IP网络共享资源，主要在unix系列操作系统上使用…...

编程日记 2025/7/17 6:42:15

【人工智能】Python常用库-Scikit-learn常用方法教程

Scikit-learn 是一个功能强大的机器学习库，支持数据预处理、分类、回归、聚类、降维等功能，广泛用于模型开发与评估。以下是 Scikit-learn 的常用方法及详细说明。 1. 安装与导入安装 Scikit-learn： pip install scikit-learn导入基本模块…...

编程日记 2025/7/15 18:08:19

sargo 官方镜像刷机

资料官方镜像https://developers.google.cn/android/images?hlzh-cn zip镜像 https://googledownloads.cn/dl/android/aosp/sargo-rq3a.211001.001-factory-2a1befea.zip 使用 fastboot 刷写下载好的镜像步骤先使用命令 adb reboot bootloader 再使用./falsh-all.sh 命…...

编程日记 2025/7/12 16:59:32

解决首次加载数据空指针异常

起初效果： 使用async...await异步加载数据最终效果： 代码： <template><div class"user-list-container"><div v-if"loading" class"loading">正在加载用户数据..…...

编程日记 2025/7/17 10:54:00

BERT的中文问答系统35

优化GUI布局、显示问答内容、增加自动搜索功能等。以下是完整的项目结构和代码： 项目结构 xihe241117/ ├── data/ │ └── train_data.jsonl ├── logs/ ├── models/ │ └── xihua_model.pth ├── requirements.txt ├── README.md └── 智…...

编程日记 2025/7/14 1:27:26

若依框架部署在网站一个子目录下（/admin）问题（

部署在子目录下首先修改vue.config.js文件： 问题一：登陆之后跳转到了404页面问题，解决办法如下： src/router/index.js 把404页面直接变成了首页（大佬有啥优雅的解决办法求告知） 问题二：退出登录…...

编程日记 2025/7/15 8:42:04

DB2数据库

DB2数据库是IBM公司开发的一种关系数据库管理系统（RDBMS），它支持多种数据模型，包括关系模型、文档模型、图模型等。DB2最初是为大型机环境设计的，但现在它已扩展到各种平台，包括Windows、Linux和Unix等&…...

编程日记 2025/7/15 22:43:33

python excel接口自动化测试框架！

今天采用Excel继续写一个接口自动化测试框架。设计流程图这张图是我的excel接口测试框架的一些设计思路。首先读取excel文件，得到测试信息，然后通过封装的requests方法，用unittest进行测试。其中，接口关联的参数通过正则进…...

编程日记 2025/7/13 4:29:37

Spring框架整合单元测试

目录一、配置文件方式 1.导入依赖 2.编写类和方法 3.配置文件applicationContext-test.xml 4.测试类 5.运行结果二、全注解方式 1.编写类和方法 2.配置类 3.测试类 4.运行结果每次进行单元测试的时候，都需要编写创建工厂，加载配置文件等相关…...

编程日记 2025/7/14 15:25:02

Java部分新特性

模式匹配 instance of 模式匹配之前写法 public void print(Object o) {if (o instanceof String){String str (String) obj;System.out.println("This is a String of length " s.length());} else {System.out.println("This is not a String");} …...

编程日记 2025/7/15 22:09:49

keepalived+lVS(dr)高可用集群

keepalivedlVS(dr)高可用集群规划服务器名称IP描述masterkeepalivedlvsVIP:192.168.238.100DIP:192.168.238.151keepalived的master节点和lvs负载均衡backupkeepalivedlvsVIP:192.168.238.100DIP:192.168.238.152keepalived的备份节点和lvs负载均衡server1VIP:192.168.238.…...

编程日记 2025/7/11 20:04:23

【前端】JavaScript中的柯里化（Currying）详解及实现

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: 前端文章目录 💯前言💯什么是柯里化？💯柯里化的特点💯柯里化的简单示例💯通用的柯里化实现💯柯里化让代码更易读的原因&#x1f4af…...

编程日记 2025/7/17 10:56:16

Cyberchef 辅助网络安全运营-数据格式转换

在网络安全的世界中，经常会遇到各种格式的数据，比如二进制，比如说16进制，URL编码，HTML编码，Unicode编码，Base格式的编码。网络安全运营一个明确的目标就是把这些不同的数据格式换成为可读的字符…...

编程日记 2025/7/14 7:19:09

鸿蒙面试 --- 性能优化（精简版）

一、性能优化的三个方面感知流畅：通过合理运用动画提升用户对应用操作的感知流畅度，同时避免因动画滥用导致性能下降。涵盖视觉感知优化、转场场景动效感知流畅（如出现 / 消失转场、导航转场、模态转场、共享元素转场等）&#x…...

编程日记 2025/7/14 11:12:09

qsort函数详解+代码展示

文章目录概要系列文章目录前言(1) 定义(2) 使用（举例子上代码）1、定义数组：2、定义比较函数：3、调用 qsort：4、输出结果： (3) 注意事项小结概要本篇博客将详细地介绍qsort排序函数，&#x…...

编程日记 2025/7/17 9:42:44

ms-hot29 解码方法

leetcode原题链接: 解码方法 ms-hot目录: ms-hot目录上一篇：ms-hot28 合并两个有序数组下一篇：二叉树的中序遍历题目描述一条包含字母 A-Z 的消息通过以下映射进行了编码 ： "1" -> A "2"…...

编程日记 2025/7/13 11:25:07

【5】STM32·FreeRTOS·临界段保护与调度器挂起

目录一、临界段代码保护简介二、临界段代码保护函数介绍 2.1、调用示例 2.2、内部实现三、任务调度器的挂起和恢复 3.1、调用示例 3.2、内部实现一、临界段代码保护简介什么是临界段：临界段代码也叫做临界区，是指那些必须完整运行&#xff…...

编程日记 2025/7/15 18:00:20

daos源码编译

1. 前言本文详细介绍如何在almalinux8.9上编译daos.2.0.0源码。系统环境如下： daos: 2.0.0 linux os: almalinux 8.9 linux kernel: 4.18.0-513.5.1.el8_9.x86_64之所以选择2.0.0版本，是因为daos从2.0.0开始是一个全新的架构设计&a…...

编程日记 2025/7/13 20:10:00

Flink--API 之Transformation-转换算子的使用解析

目录一、常用转换算子详解 （一）map 算子 （二）flatMap 算子 （三）filter 算子 （四）keyBy 算子元组类型 POJO （五）reduce 算子二、合并与连接操作 …...

编程日记 2025/7/7 5:34:49

火山引擎VeDI在AI+BI领域的演进与实践

随着数字化时代的到来，企业对于数据分析与智能决策的需求日益增强。作为新一代企业级数据智能平台，火山引擎数智平台VeDI基于字节跳动多年的“数据驱动”实践经验，也正逐步在AI（人工智能）与BI（商业智能&…...

编程日记 2025/7/9 10:00:41

java获取docker镜像构建日志

在Java中获取Docker镜像的构建日志，你可以使用Docker Engine API。以下是一个使用OkHttp库的示例代码，用于获取构建日志： import okhttp3.*; import java.io.IOException; public class DockerLogsFetcher { private static final St…...

编程日记 2025/7/13 1:14:21

Spring-boot整合Webservice服务端

Spring Boot整合Webservice服务端本文是基于前辈一顿吃不饱的文章SpringBoot整合WebService（服务端客户端）-CSDN博客，由于工作需要用.NET调用其他系统发布的WebService服务，尝试用java搭建一个WebService服务端测试一下&#xf…...

编程日记 2025/7/15 14:08:40

动静分离具体是怎么实现的？

在 Nginx 中实现动静分离是一种常见的优化手段，用于提高网站的性能和可扩展性。以下是 Nginx 动静分离的一些基本概念和配置方法： 1、什么是动静分离： 动静分离是指将网站的静态资源（如图片、CSS、JavaScript 文件）与…...

编程日记 2025/7/13 1:10:07

如何取出.vmdk文件中的数据

前提：我的云服务器到期了，于是我将云服务器导出了.vmdk镜像。本想在vm虚拟机中启动，但是一直报错。很是苦恼。首先下载DiskGenius这个软件。点击磁盘-》打开磁盘打开.vmdk文件可以看到内部的文件了，可以选择对应文件导出到桌…...

编程日记 2025/7/14 22:27:03

Vue2中 vuex 的使用

1.安装 vuex 安装vuex与vue-router类似，vuex是一个独立存在的插件，如果脚手架初始化没有选 vuex，就需要额外安装。 yarn add vuex3 或者 npm i vuex3 233 Vue2 Vue-Router3 Vuex3 344 Vue3 Vue-Router4 Vuex4 2. 新建 store/index.j…...

编程日记 2025/7/12 22:59:40