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

堆的介绍与堆的实现和调整

个人主页:Lei宝啊

愿所有美好如期而遇


目录

​​堆的介绍:

关于堆的实现及相关的其他问题:

堆的初始化:

堆的销毁:

插入建堆:

堆向上调整:

交换两个节点的值:

堆向下调整:

删除根节点:

求堆顶数据:

打印堆的每一个节点的值:

堆排序:

堆的节点数量:

判断堆是否为空:

创建一个多数据文件:

TopK问题(综合):

向上/向下调整建堆哪个时间复杂度更优秀?


​​堆的介绍:

首先,堆是不完全二叉树。

不完全二叉树:除了最后一层外,其他层每一层都是满的,最后一层节点从左到右排。

再者,堆分为大堆和小堆

大堆:父母节点的值大于等于孩子节点

小堆:父母节点的值小于等于孩子节点

关于堆的实现及相关的其他问题:

我们在主函数中将定义一个Heap hp;

typedef int Heaptype;
typedef struct Heap
{Heaptype* data;int size;int capacity;
}Heap;//堆的初始化
void HeapInit(Heap* php);
//堆的销毁
void HeapDestroy(Heap* php);
//插入建堆
void HeapPush(Heap* php, Heaptype num);
//堆向上调整
void Ajustup(Heaptype* a, int child);
//交换两个节点的值
void Swap(Heaptype* p1, Heaptype* p2);
//堆向下调整
void AjustDown(Heaptype* a, int n, int parent);
//删除根节点
void HeapPop(Heap* php);
//求得堆顶数据
Heaptype HeapTop(Heap* php);
//打印堆的每一个节点的值
void HeapPrint(Heaptype* arr, int size);
//堆排序
void HeapSort(Heaptype* arr, int size);
//堆的节点数量
void HeapSize(Heap* php);
//判读堆是否为空
void HeapEmpty(Heap* php);
//创建一个多数据文件
void CreateNDate();
//TopK问题
void PrintTopK(int k);

堆的初始化:

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

堆的销毁:

void HeapDestroy(Heap* php)
{assert(php);free(php->data);php->data = NULL;php->size = 0;php->capacity = 0;
}

插入建堆:

void HeapPush(Heap* php, Heaptype num)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;Heaptype* temp = (Heaptype*)realloc(php->data, sizeof(Heaptype) * newcapacity);if (temp == NULL){perror("realloc fail");printf("\n%s", __LINE__);}php->data = temp;php->capacity = newcapacity;}php->data[php->size++] = num;//插入后当即向上调整,以保证还是个堆Ajustup(php->data, php->size - 1);
}

堆向上调整:

//堆向上调整,调整一轮,建堆就循环插入去建
void Ajustup(Heaptype* a, int child)
{int parent = (child - 1) / 2;//当child == 0 的时候,parent也为0while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

交换两个节点的值:


void Swap(Heaptype* p1, Heaptype* p2)
{Heaptype temp = *p1;*p1 = *p2;*p2 = temp;}

堆向下调整:

//堆向下调整
void AjustDown(Heaptype* a, int n, int parent)
{//从叶子节点开始int child = parent * 2 + 1;while (child < n){//找出最小孩子if (child + 1 < n && a[child] > a[child + 1]){child++;}else{if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}	else{break;}}}}

删除根节点:

void HeapPop(Heap* php)
{assert(php);assert(php->size > 0);Swap(&php->data[0], &php->data[php->size - 1]);AjustDown(php->data, php->size - 1, 0);php->size--;
}

求堆顶数据:

Heaptype HeapTop(Heap* php)
{assert(php);return php->data[0];
}

打印堆的每一个节点的值:

void HeapPrint(Heaptype* arr, int size)
{assert(arr);for (int i = 0; i < size; i++){printf("%d ", arr[i]);}
}

堆排序:

void HeapSort(Heaptype* arr, int size)
{assert(arr);//向上调整建堆(小堆)/*int num = size;for (int i = 0; i < num; i++){Ajustup(arr, i);}*///向下调整建堆int last = (size - 1 - 1) / 2;for (int i = last; i >= 0; i--){AjustDown(arr, size, i);}//排序int end = size - 1;while (end > 0){Swap(&arr[0], &arr[end]);AjustDown(arr, end, 0);end--;}
}

堆的节点数量:

void HeapSize(Heap* php)
{assert(php);return php->size;
}

判断堆是否为空:

void HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

创建一个多数据文件:

void CreateNDate()
{int n = 10000;srand((unsigned int)time(NULL));const char* file = "heap.txt";FILE* pf = fopen(file, "w");{if (pf == NULL){perror("fopen fail");return;}}for (int i = 0; i < n; i++){int num = rand() % 1000000;fprintf(pf, "%d\n", num);}fclose(pf);}

TopK问题(综合):

void PrintTopK(int k)
{Heaptype* arr = (Heaptype*)malloc(sizeof(Heaptype) * k);	if (arr == NULL){perror("malloc fail");return;}FILE* pf = fopen("heap.txt", "r");if (pf == NULL){perror("fopen fail");return;}for (int i = 0; i < k; i++){fscanf(pf, "%d", &arr[i]);}//调整为小堆int n = (k - 1 - 1) / 2;for (int i = n; i >= 0; i--){AjustDown(arr, k, i);}//由于我们建1的是大小为k的堆,堆顶的数值最小,当新的数据大于堆//顶时,进堆,而堆顶的数据被替换,之后堆向下调整int a = 0;while (fscanf(pf, "%d", &a) != EOF){if (a > arr[0]){arr[0] = a;AjustDown(arr, k, 0);}}//此时堆里的数据是最大的k个数	for (int i = 0; i < k; i++){printf("%d ", arr[i]);}fclose(pf);free(arr);
}

向上/向下调整建堆哪个时间复杂度更优秀?

答案是堆向下调整,时间复杂度为O(N),堆向上调整时间复杂度为O(N*logN)。


相关文章:

堆的介绍与堆的实现和调整

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 目录 ​​堆的介绍&#xff1a; 关于堆的实现及相关的其他问题&#xff1a; 堆的初始化&#xff1a; 堆的销毁&#xff1a; 插入建堆&#xff1a; 堆向上调整&#xff1a; 交换两个节点的值&#xff1a; 堆向下调整&a…...

【广州华锐互动】马属直肠检查3D虚拟仿真课件

随着科技的发展&#xff0c;医疗行业也在不断地进行创新。其中&#xff0c;广州华锐互动开发的马属直肠检查3D虚拟仿真课件&#xff0c;为医学教育和实践操作带来了新的可能性。它不仅可以帮助医生提高诊断准确率&#xff0c;还可以让医学生在没有真实病人的情况下进行实践操作…...

Nuxt 菜鸟入门学习笔记:路由

文章目录 路由 Routing页面 Pages导航 Navigation路由参数 Route Parameters路由中间件 Route Middleware路由验证 Route Validation Nuxt 官网地址&#xff1a; https://nuxt.com/ 路由 Routing Nuxt 的一个核心功能是文件系统路由器。pages/目录下的每个 Vue 文件都会创建一…...

C++基本语法和注释

C程序介绍 C 程序可以定义为对象的集合&#xff0c;这些对象通过调用彼此的方法进行交互。现在让我们简要地看一下什么是类、对象&#xff0c;方法、即时变量。 对象 - 对象具有状态和行为。例如&#xff1a;一只狗的状态 - 颜色、名称、品种&#xff0c;行为 - 摇动、叫唤、吃…...

CSRF攻击

防御策略 过滤判断换referer头&#xff0c;添加tocken令牌验证&#xff0c;白名单 CSRF攻击和XSS比较 相同点&#xff1a;都是欺骗用户 不同点&#xff1a; XSS有攻击特征&#xff0c;所有输入点都要考虑代码&#xff0c;单引号过滤 CSRF没有攻击特征&#xff0c;利用的点…...

2023 “华为杯” 中国研究生数学建模竞赛(D题)深度剖析|数学建模完整代码+建模过程全解全析

问题一&#xff1a;区域碳排放量以及经济、人口、能源消费量的现状分析 思路&#xff1a; 定义碳排放量 Prediction 模型: CO2 P * (GDP/P) * (E/GDP) * (CO2/E) 其中: CO2:碳排放量 P:人口数量 GDP/P:人均GDP E/GDP:单位GDP能耗 CO2/E:单位能耗碳排放量 2.收集并统计相关…...

【Proteus仿真】【STM32单片机】基于单片机的智能晾衣架控制系统

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 系统运行后&#xff0c;LCD1604显示传感器检测的温湿度、光线强度和风速&#xff0c;工作模式&#xff0c;以及相应阈值&#xff0c;系统工作状态等&#xff1b;系统默认为自动模式&#xff0c; 可通过K4…...

C/C++代码静态检测工具PC-Lint常见错误总结

目录 1、PC-Lint 概述 2、PC-lint 常见错误列举 3、PC-Lint报告的语法错误 4、总结 VC常用功能开发汇总&#xff08;专栏文章列表&#xff0c;欢迎订阅&#xff0c;持续更新...&#xff09;https://blog.csdn.net/chenlycly/article/details/124272585C软件异常排查从入门到…...

概率深度学习建模数据不确定性

https://zhuanlan.zhihu.com/p/568912284理解论文 What uncertainties do we need in Bayesian deep learning for computer vision? &#xff08;NeurIPS 2017) [1]中的数据不确定性建模&#xff0c;并给出公式推导。论文[1]指出不确定性uncertainty分为随机不确定性(aleator…...

Jenkins自动化部署前后端分离项目 (svn + Springboot + Vue + maven)有图详解

1. 准备工作 本文的前后端分离项目&#xff0c;技术框架是&#xff1a; Springboot Vue Maven SVN Redis Mysql Nginx JDK 所以首先需要安装以下&#xff1a; 在腾讯云服务器OpenCLoudOS系统中安装jdk&#xff08;有图详解&#xff09; 在腾讯云服务器OpenCLoudOS系统…...

【ELK】日志系统部署

一、ELK日志分析系统 1、ELK的组成 ElasticSearchLogStashKibana ELK基于这三个开源日志的收集、存储、检索和可视化的解决方案&#xff1b;可帮助用户快速定位和分析应用程序的故障&#xff0c;监控应用程序性能和安全&#xff0c;以及提供丰富的数据分析和展示功能。 2、完…...

【算法挨揍日记】day08——30. 串联所有单词的子串、76. 最小覆盖子串

30. 串联所有单词的子串 30. 串联所有单词的子串 题目描述&#xff1a; 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如&#xff0c;如果 words ["…...

SpringCloud Gateway--网关服务基本介绍和基本原理

&#x1f600;前言 本篇博文是关于SpringCloud Gateway的基本介绍&#xff0c;希望你能够喜欢 &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的满意是我的动力…...

使用Vue-cli构建spa项目及结构解析

一&#xff0c;Vue-cli是什么&#xff1f; 是一个官方发布的Vue脚手架工具&#xff0c;用于快速搭建Vue项目结构&#xff0c;提供了现代前端开发所需要的一些基础功能&#xff0c;例如&#xff1a;Webpack打包、ESLint语法检查、单元测试、自动化部署等等。同时&#xff0c;Vu…...

自定义Unity组件——AudioManager(音频管理器)

需求描述 在游戏开发中&#xff0c;音频资源是不可或缺的&#xff0c;通常情况下音频资源随机分布&#xff0c;各个音频的操作和管理都是各自负责&#xff0c;同时对于音频的很多操作逻辑都是大同小异的&#xff0c;这就造成了许多冗余代码的堆叠&#xff0c;除此之外在获取各类…...

leetcode 558 设计内存文件系统

题目 Design an in-memory file system to simulate the following functions: ls: Given a path in string format. If it is a file path, return a list that only contains this files name. If it is a directory path, return the list of file and directory namesin th…...

Haproxy负载均衡群集

HAproxy搭建Web群集一、Web集群调度器1、常见的Web集群调度器2、常用集群调度器的优缺点&#xff08;LVS ,Nginx,Haproxy)2.1 Nginx2.2 LVS2.3 Haproxy 3、LVS、Nginx、HAproxy的区别 二、Haproxy1、简介2、Haproxy应用分析3、HAProxy的主要特性4、Haproxy调度算法&#xff08;…...

什么是面包屑导航?

面包屑导航(Breadcrumb Navigation)这个概念来自童话故事“汉赛尔和格莱特”&#xff0c;当汉赛尔和格莱特穿过森林时&#xff0c;不小心迷路了&#xff0c;但是他们发现沿途走过的地方都撒下了面包屑&#xff0c;让这些面包屑来帮助他们找到回家的路。 在网站应用中&#xff0…...

VS2019创建GIt仓库时剔除文件或目录

假设本地有解决方案“SomeSolution” 1、首先”团队资源管理器“-“创建Git存储库”&#xff0c;选择“仅限本地”、“创建” VS会在解决方案目录下自动生成.gitattributes、.gitignore 2、编辑gitignore&#xff0c;直接拖到VS里或者用记事本打开。添加要剔除的文件或文件夹…...

计算机等级考试—信息安全三级真题六

目录 一、单选题 二、填空题 三、综合题 一、单选题...

4步实现专业黑苹果配置:OpCore-Simplify零代码自动化解决方案

4步实现专业黑苹果配置&#xff1a;OpCore-Simplify零代码自动化解决方案 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify OpCore-Simplify是一款革命性…...

12. 本地算力不足?云服务器选型指南(高性价比+适配大模型)

001、算力困境:为什么我们需要云服务器? 从一次深夜调试说起 上周三凌晨两点,我的本地工作站风扇开始狂转——16核CPU占用率97%,64GB内存基本吃满,两块3090显卡的显存指示灯红得发烫。屏幕上正在跑一个7B参数的模型微调任务,进度条卡在23%已经半小时没动过。终端里突然…...

实战指南:基于快马平台与comfyui,快速构建带姿势控制的人像卡通化应用

今天想和大家分享一个特别实用的技术方案&#xff1a;如何用ComfyUI快速搭建一个带姿势控制的人像卡通化应用。这个方案特别适合需要批量生成统一风格头像、制作产品海报等场景&#xff0c;我自己在实际工作中就经常用到。 首先说说为什么选择ComfyUI。它是一个基于节点的工作流…...

HardSourceWebpackPlugin故障排除:7个常见问题及解决方案

HardSourceWebpackPlugin故障排除&#xff1a;7个常见问题及解决方案 【免费下载链接】hard-source-webpack-plugin 项目地址: https://gitcode.com/gh_mirrors/ha/hard-source-webpack-plugin HardSourceWebpackPlugin 是 Webpack 生态系统中一个强大的缓存插件&#…...

UE Viewer终极指南:如何快速浏览和提取虚幻引擎1-4游戏资源

UE Viewer终极指南&#xff1a;如何快速浏览和提取虚幻引擎1-4游戏资源 【免费下载链接】UEViewer Viewer and exporter for Unreal Engine 1-4 assets (UE Viewer). 项目地址: https://gitcode.com/gh_mirrors/ue/UEViewer UE Viewer是一款专为虚幻引擎1-4游戏资源打造…...

AI绘画新体验:灵毓秀-牧神-造相Z-Turbo快速入门,小白也能画古风女神

AI绘画新体验&#xff1a;灵毓秀-牧神-造相Z-Turbo快速入门&#xff0c;小白也能画古风女神 1. 认识灵毓秀-牧神-造相Z-Turbo 1.1 什么是灵毓秀-牧神-造相Z-Turbo 灵毓秀-牧神-造相Z-Turbo是一款专门用于生成《牧神记》中灵毓秀角色图像的AI绘画模型。它基于Xinference框架部…...

猫抓资源嗅探扩展:网页媒体资源提取的完整解决方案

猫抓资源嗅探扩展&#xff1a;网页媒体资源提取的完整解决方案 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 在现代互联网浏览体验中&#xff0c…...

主流AI培训机构评测:关键指标全对比

引言 随着AI技术的飞速发展&#xff0c;AI培训市场也日益繁荣。然而&#xff0c;无论是企业还是创业者在选择AI培训机构时&#xff0c;都面临着诸多挑战。企业端存在缺乏数字化运营团队、不懂AI工具使用、短视频内容生产效率低、打造个人IP能力不足、同城获客成本高且精准度低…...

2025年大中华区21个主要城市甲级写字楼市场数据

、大中华区主要城市甲级写字楼市场数据速览(2025年)美通社消息&#xff1a;全球领先的房地产服务公司戴德梁行发布《大中华区写字楼供应/需求前沿趋势》年度报告&#xff0c;针对2025年大中华区21个主要城市甲级写字楼市场的整体表现展开研究&#xff0c;聚焦市场供需关系深入分…...

节出来的 00 后,没做聊天壳子,先盯上了你的 Enter 键

字节出来的 00 后&#xff0c;没做聊天壳子&#xff0c;先盯上了你的 Enter 键你以为桌面 AI 助手还停留在「我问一句&#xff0c;它答一句」的阶段&#xff0c;这帮 00 后已经想把事做得更狠一点了。AirJelly 最近放出内测版&#xff0c;路子很野。它不是单纯陪你聊天&#xf…...