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

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

目录

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.…...

数据分析的尽头是web APP?

数据分析的尽头是web APP&#xff1f; 在做了一些数据分析的项目&#xff0c;也制作了一些数据分析相关的web APP之后&#xff0c;总结自己的一些想法和大家分享。 1.web APP是呈现数据分析结果的另外一种形式。 数据分析常见的结果是数据分析报告&#xff0c;可以是PPT或者…...

YOLO系列论文综述(从YOLOv1到YOLOv11)【第3篇:YOLOv1——YOLO的开山之作】

YOLOv1 1 摘要2 YOLO: You Only Look Once2.1 如何工作2.2 网络架构2.3 训练2.4 优缺点 YOLO系列博文&#xff1a; 【第1篇&#xff1a;概述物体检测算法发展史、YOLO应用领域、评价指标和NMS】【第2篇&#xff1a;YOLO系列论文、代码和主要优缺点汇总】 ——————————…...

容器和它的隔离机制

什么是容器和它的隔离机制&#xff1f; 容器 是一种轻量化的虚拟化技术&#xff0c;它允许多个应用程序共享同一个操作系统&#xff08;OS&#xff09;内核&#xff0c;同时为每个应用程序提供自己的运行环境。容器通过利用 Linux 的内核功能&#xff08;如 Namespaces 和 Cgr…...

【数据结构与算法】排序算法总结:冒泡 / 快排 / 直接插入 / 希尔 / 简单选择 / 堆排序 / 归并排序

1 排序 1.1 冒泡 内排序的交换排序类别 1.1.1 普通实现 public class BubbleSort {/*** 基本的 冒泡排序*/public static void bubbleSort(int[] srcArray) {int i,j; // 用于存放数组下标int temp 0; // 用于交换数值时临时存放值for(i0;i<srcArray.length-1;i){// j …...

Windows Serv 2019 虚拟机 安装Oracle19c,图文详情(超详细)

1、下载安装文件 Oracle官网下载直链&#xff1a;https://www.oracle.com/database/technologies/oracle-database-software-downloads.html#db_ee 夸克网盘下载&#xff1a;https://pan.quark.cn/s/1460a663ee83 2、新建 Windows Server 2019 虚拟机 &#xff08;超详细&a…...

数字孪生开发之 Three.js 插件资源库(2)

在当今数字化快速发展的时代&#xff0c;数字孪生技术正逐渐成为各个领域的关键技术之一。它通过创建物理实体的虚拟副本&#xff0c;实现对实体的实时监测、模拟和优化&#xff0c;为企业和组织带来了诸多好处&#xff0c;如提高生产效率、降低成本、改进产品质量等。然而&…...

小米C++ 面试题及参考答案下(120道面试题覆盖各种类型八股文)

指针和引用的区别?怎么实现的? 指针和引用有以下一些主要区别。 从概念上来说,指针是一个变量,它存储的是另一个变量的地址。可以通过指针来间接访问所指向的变量。例如,我们定义一个整型指针int *p;,它可以指向一个整型变量的内存地址。而引用是一个别名,它必须在定义的…...

OpenOCD之J-Link下载

NOTE&#xff1a;此篇文章由笔者的 VSCode编辑GCC for ARM交叉编译工具链Makefile构建OpenOCD调试&#xff08;基于STM32的标准库&#xff09;派生而来。 1.下载USB Dirver Tool.exe&#xff0c;选择J-Link dirver&#xff0c;替换成WinUSB驱动。&#xff08;⭐USB Dirver Tool…...

华为云云连接+squid进行正向代理上网冲浪

1 概述 ‌Squid‌是一个高性能的代理缓存服务器&#xff0c;主要用于缓冲Internet数据。它支持多种协议&#xff0c;包括FTP、gopher、HTTPS和HTTP。Squid通过一个单独的、非模块化的、I/O驱动的进程来处理所有的客户端请求&#xff0c;这使得它在处理请求时具有较高的效率‌。…...

情绪识别项目

文章目录 1、mp4s文件转mp3文件2、Audition下载3、Audition安装4、Audition使用&#xff1a; 1、mp4s文件转mp3文件 在线转&#xff1a;Convert audio to MP3&#xff08;https://audio.online-convert.com/convert-to-mp3&#xff09; 2、Audition下载 Audition CC2019/64位…...

【RISC-V CPU debug 专栏 2.2 -- Hart DM States】

文章目录 Hart DM StatesHart 的 DM 状态1. 不存在(Non-existent)2. 不可用(Unavailable)3. 运行(Running)4. 暂停(Halted)状态转换与复位行为状态指示信号Hart DM States 在 RISC-V 调试架构中,每个可以被选择的硬件线程(hart)处于以下四种调试模块(DM)状态之一…...

从零样本到少样本学习:一文读懂 Zero-shot、One-shot 和 Few-shot 的核心原理与应用!

爆款标题&#xff1a; 《从零样本到少样本学习&#xff1a;一文读懂 Zero-shot、One-shot 和 Few-shot 的核心原理与应用&#xff01;》 正文&#xff1a; 在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;Zero-shot、One-shot 和 Few-shot 学习已经成为衡量大语言…...

【LC】3101. 交替子数组计数

题目描述&#xff1a; 给你一个二进制数组nums 。如果一个子数组中 不存在 两个 相邻 元素的值 相同 的情况&#xff0c;我们称这样的子数组为 交替子数组 。返回数组 nums 中交替子数组的数量。 示例 1&#xff1a; 输入&#xff1a; nums [0,1,1,1] 输出&#xff1a; 5 …...

如何构建SAAS项目

在后台使用JDBC方式动态创建用户输入的数据库信息&#xff08;库名、地址、用户名、密码&#xff09; 执行预先写好的sql文件&#xff08;如mybatis的scriptRunner)执行建表语句及插入基础数据&#xff08;管理员用户、普通用户&#xff09;...

树莓派搭建NextCloud:给数据一个安全的家

前言 NAS有很多方案&#xff0c;常见的有 Nextcloud、Seafile、iStoreOS、Synology、ownCloud 和 OpenMediaVault &#xff0c;以下是他们的特点&#xff1a; 1. Nextcloud 优势&#xff1a; 功能全面&#xff1a;支持文件同步、共享、在线文档编辑、视频会议、日历、联系人…...

深入解读 MongoDB 查询耗时:Execution 和 Fetching 阶段详解

在使用 MongoDB 时&#xff0c;查询性能的分析与优化是开发者关注的重点。MongoDB 的查询过程通常分为两个主要阶段&#xff1a;Execution&#xff08;执行阶段&#xff09;和Fetching&#xff08;拉取阶段&#xff09;。每个阶段的耗时代表不同的性能瓶颈&#xff0c;优化思路…...

frida_hook_dlopen(当年到lib目录下找发现一个so都没有,hook下dlopen)

Frida 脚本用于拦截 Android 应用程序中的 dlopen 和 android_dlopen_ext 函数。这两个函数用于动态加载共享库&#xff0c;脚本通过拦截这些函数的调用来记录加载的库的路径。 代码分析 var dlopen Module.findExportByName(null, "dlopen"); // 6.0 var android…...

Zero to JupyterHub with Kubernetes中篇 - Kubernetes 常规使用记录

前言&#xff1a;纯个人记录使用。 搭建 Zero to JupyterHub with Kubernetes 上篇 - Kubernetes 离线二进制部署。搭建 Zero to JupyterHub with Kubernetes 中篇 - Kubernetes 常规使用记录。搭建 Zero to JupyterHub with Kubernetes 下篇 - Jupyterhub on k8s。 参考&…...

WordCloud去掉停用词(fit_words+generate)的2种用法

-------------词云图集合------------- WordCloud去掉停用词&#xff08;fit_wordsgenerate&#xff09;的2种用法 通过词频来绘制词云图&#xff08;jiebaWordCloud&#xff09; Python教程95&#xff1a;去掉停用词词频统计jieba.tokenize示例用法 将进酒—李白process_t…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...