当前位置: 首页 > 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…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...