【数据结构】——堆的实现与算法

目录

一、堆的实现

1.1堆数据的插入

1.2堆数据的删除

二、建堆算法

2.1向上调整建堆

2.2向下调整建堆

三、堆的应用

3.1堆排序

3.2Top—K问题


一、堆的实现

1.1堆数据的插入

插入一个数据后不再是小堆需要将新数据调整到合适的位置,所以堆的插入就是在数组插入数据再向上调整即可

堆数据的插入

1.检查空间是否需要扩容

2.赋值size++

3.向上调整

void AdjustUp(HPDataType* a,int size)
{int child = size - 1;while (child > 0){int parent = (child - 1) / 2;//父亲结点if (a[child] < a[parent])//判断 小于建小堆{Swap(&a[child], &a[parent]);child = parent;}else{break;}}
}
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType)*newcapacity);//这是 php->a的动态内存if (tmp == NULL){perror("fail realloc");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size++] = x;AdjustUp(php->a, php->size);
}

1.2堆数据的删除

分析:

因此:

代码:

void AdjustDown(HPDataType* a, int size, int parent)
{int child = 2 * parent + 1;while (child<size)//结束条件不能越界{//假设法求出最小的孩子if (child + 1 < size && a[child] > a[child + 1]){child = child + 1;}//调整if (a[parent] > a[child]){Swap(&a[parent], &a[child]);//更新父亲孩子结点parent = child;child = 2 * parent + 1;}else{break;}}
}
void HPPop(HP* php)//删除根结点
{assert(php && php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

二、建堆算法

2.1向上调整建堆

堆插入的过程其实就是建堆,在一个堆的末尾插入数据然后向上调整形成一个新的堆

void AdjustUp(HPDataType* a, int size)
{int child = size - 1;while (child > 0){int parent = (child - 1) / 2;//父亲结点if (a[child] > a[parent])//判断 小于建小堆{Swap(&a[child], &a[parent]);child = parent;}else{break;}}
}

向上调整建堆时间复杂度分析

根据大O渐进法,向上调整建堆的时间复杂度即 O(N*logN)

2.2向下调整建堆

从最后一个父亲结点开始依次向下调整

根据大O渐进法,向下调整建堆的时间复杂度即 O(N)

对比向上调整建堆,h-1层向下调整只需要移动1层,而向上调整需要移动h-1次因此向下调整是更优的建堆算法

三、堆的应用

3.1堆排序

堆排序即利用堆的思想来进行排序,总共分为两个步骤:

1. 建堆

升序:建大堆

降序:建小堆

2. 利用堆删除思想来进行排序 

演示代码:

//升序向下调整
void SAdjustDown(HPDataType* a, int size, int parent)
{int child = 2 * parent + 1;while (child < size)//结束条件不能越界{//假设法求出最小的孩子if (child + 1 < size && a[child] < a[child + 1]){child = child + 1;}//调整if (a[parent] < a[child]){Swap(&a[parent], &a[child]);//更新父亲孩子结点parent = child;child = 2 * parent + 1;}else{break;}}
}void HeapSort(int* a, int n)
{//升序建大堆//降序建小堆向上建堆//for (int i = 1; i < n; i++)//{//	//相当于慢慢插入数据建堆//	SAdjustUp(a, i);//}//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){SAdjustDown(a, n,  i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);SAdjustDown(a, end, 0);end--;}
}

 堆排序的时间复杂度:

对比向上调整建堆

可以知道堆排序时间复杂度:O(N*logN)

3.2Top—K问题

Top—K问题:N个数中求最大的(最小的)前K个数据,一般N远大于K

实例:专业前5名、富豪榜、游戏战力榜等等

方法一:

建一个N个数的大堆  O(N)

Pop k次数据         O(N*logN)

此方法缺陷也很明显如果N太大,排序就不太可取,甚至数据都无法一下子加载到内存中

方法二:

用前K个数建一个小堆   O(K)

剩下数据与堆顶数据比较,如果比堆顶数据大,那么替代堆顶进堆(覆盖堆顶数据然后向下调整)

O(logK*(N-K)(最坏情况都需要覆盖调整)

复杂度:O(N)

分析:

剩下的N-K个数据依次与堆顶数据比较

<1>数据比堆顶数据小,那么不可能为最大的前K个

<2>数据比堆顶数据大,覆盖调整之后形成一个新的小堆,再次比较

比较完所有的数后那么小堆中就是最大的前K个数据

代码实现

先生成十万个数据

void CreatData()
{int n = 100000;//生成10万个数据srand(time(0));//生成不同的种子FILE* file = fopen("qsy.txt", "w");//打开文件for (int i = 0; i < n; i++){int x = rand() % 100001 + i;//生成随机数fprintf(file, "%d\n", x);//写数据}fclose(file);//关闭文件file = NULL;
}

开K个空间从 qsy 文件里读取数据建堆

之后再读取数据比较堆顶数据覆盖调整

void CreatData()
{int n = 100000;//生成10万个数据srand(time(0));//生成不同的种子FILE* file = fopen("qsy.txt", "w");//打开文件for (int i = 0; i < n; i++){int x = rand() % 100001 + i;//生成随机数fprintf(file, "%d\n", x);//写数据}fclose(file);//关闭文件file = NULL;
}int main()
{CreatData();int k;scanf("%d", &k);int* kmin = (int*)malloc(10 * sizeof(int));if (kmin == NULL){perror("malloc fail");return 1;}//读取数据FILE* pf = fopen("qsy.txt", "r");for (int i = 0; i < k; i++){fscanf(pf, "%d", &kmin[i]);}//建k个数的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){JAdjustDown(kmin, k, i);}//比较数据int x;while (fscanf(pf, "%d", &x) != EOF){if (x > kmin[0]){kmin[0] = x;JAdjustDown(kmin, k, 0);}}//打印数据for (int i = 0; i < k; i++){printf("%d ", kmin[i]);}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/388027.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

类和对象(中 )C++

默认成员函数就是用户不显示实现&#xff0c;编译器会自动实现的成员函数叫做默认成员函数。一个类&#xff0c;我们在不写的情况下&#xff0c;编译器会自动实现6个默认成员函数&#xff0c;需要注意&#xff0c;最重要的是前4个&#xff0c;其次就是C11以后还会增加两个默认成…

onlyoffice用nginx反向代理

我对于onlyoffice的需求就是当个在线编辑器使用。在集成react的时候之前都是写的绝对路径的地址&#xff0c;这样在需要迁移应用的时候就造成了巨大的麻烦&#xff0c;所以我决定用nginx做反向代理&#xff0c;这样我集成的时候就不用每次都修改源码中的地址了。 一开始写的代…

昇思25天学习打卡营第XX天|基于MindSpore通过GPT实现情感分类

其实数据集和模型的其他大平台接口的&#xff0c;感觉不用非包在自己包里 %env HF_ENDPOINThttps://hf-mirror.com mindnlp.transformers 库中的 GPTTokenizer 类来加载和处理与GPT&#xff08;生成式预训练变换器&#xff09;模型兼容的分词器&#xff0c;并添加特殊的控制标…

Spring源码(八)--Spring实例化的策略

Spring实例化的策略有几种 &#xff0c;可以看一下 InstantiationStrategy 相关的类。 UML 结构图 InstantiationStrategy的实现类有 SimpleInstantiationStrategy。 CglibSubclassingInstantiationStrategy 又继承了SimpleInstantiationStrategy。 InstantiationStrategy I…

SpringBoot通过3种方式实现AOP切面

❃博主首页 &#xff1a; 「码到三十五」 &#xff0c;同名公众号 :「码到三十五」&#xff0c;wx号 : 「liwu0213」 ☠博主专栏 &#xff1a; <mysql高手> <elasticsearch高手> <源码解读> <java核心> <面试攻关> ♝博主的话 &#xff1a…

Sonar-Scanner: 静态代码分析的利器

Sonar-Scanner: 静态代码分析的利器 懂得享受生活的过程&#xff0c;人生才会更有乐趣。每个人都会遇到一些陷阱&#xff0c;每个人都有过去&#xff0c;有的甚至是失败的往事。过去的错误和耻辱只能说明过去&#xff0c;真正能代表人一生的&#xff0c;是他现在和将来的作为。…

【更新2022】省级农民专业合作社数量 无缺失 2006-2022

省级农民专业合作社数量是研究中国农村经济组织和农业社会化服务的重要数据。这些数据可以用来分析不同省份农业生产组织形式的多样性及其对农民生产、技术创新和收入增长的影响。研究者可以基于这些数据&#xff0c;探讨农民专业合作社在提升农产品质量、优化农业生产结构和推…

Transformer处理文本分类实例(Pytorch)

文章目录 Transformer处理文本分类实例参考网站我们构建一个实例问题,预测AG_NEWS的文本分类AG_NEWS数据集介绍预测目标总体思路(简述)主要流程数据预处理dataset构建(不是重点)构建词表 编写处理模型执行词嵌入位置编码(PositionalEncoding)(*核心)多层Transformer模块多头自注…

Mojo数据类型详解

Mojo 中的所有值都分配有相对应的数据类型&#xff0c;大多数类型都是由结构体定义的标称的类型。这些类型是标称的&#xff08;或“命名的”&#xff09;&#xff0c;因为类型相等性是由类型的名称而不是其结构决定的。 有一些类型未定义为结构&#xff0c;例如下面的两种情况…

百款精选的HTML5小游戏源码,你可以下载并直接运行在你的小程序或者自己的网站上

今天我带来了一份特别的礼物——百款精选的HTML5小游戏源码&#xff0c;你可以下载并直接运行在你的小程序或者自己的网站上&#xff0c;只需双击index.html即可开始。无论你是在寻找创意引流&#xff0c;还是想为你的网站增添互动性&#xff0c;这些小游戏都能帮你实现&#x…

办公必备!一键把PDF转换为PPT文件,只需这3款神器!

在当今数字化办公环境中&#xff0c;文件格式的转换已成为提高工作效率的关键因素之一。其中&#xff0c;PDF(便携式文档格式)和PPT(PowerPoint演示文稿)是两种广泛使用的文件格式。然而&#xff0c;有时我们需要将PDF文件转换为PPT格式&#xff0c;以便进行编辑或演示。 为方…

数据结构的基本概念与算法

数据结构的基本概念与算法 什么是数据&#xff1f; 数据是信息的载体&#xff0c;是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合&#xff1b;总结来说 -> 数据就是计算机程序加工的原料&#xff1b; 数据元素、数据项&#xf…

<数据集>棉花识别数据集<目标检测>

数据集格式&#xff1a;VOCYOLO格式 图片数量&#xff1a;13765张 标注数量(xml文件个数)&#xff1a;13765 标注数量(txt文件个数)&#xff1a;13765 标注类别数&#xff1a;4 标注类别名称&#xff1a;[Partially opened, Fully opened boll, Defected boll, Flower] 序…

Java面试——Tomcat

优质博文&#xff1a;IT_BLOG_CN 一、Tomcat 顶层架构 Tomcat中最顶层的容器是Server&#xff0c;代表着整个服务器&#xff0c;从上图中可以看出&#xff0c;一个Server可以包含至少一个Service&#xff0c;用于具体提供服务。Service主要包含两个部分&#xff1a;Connector和…

SQL labs-SQL注入(七,sqlmap对于post传参方式的注入,2)

本文仅作为学习参考使用&#xff0c;本文作者对任何使用本文进行渗透攻击破坏不负任何责任。参考&#xff1a;SQL注入之Header注入_sqlmap header注入-CSDN博客 序言&#xff1a; 本文主要讲解基于SQL labs靶场&#xff0c;sqlmap工具进行的post传参方式的SQL注入&#xff0c…

【Java版数据结构】初识泛型

看到这句话的时候证明&#xff1a;此刻你我都在努力 加油陌生人 br />个人主页&#xff1a;Gu Gu Study专栏&#xff1a;Java版数据结构 喜欢的一句话&#xff1a; 常常会回顾努力的自己&#xff0c;所以要为自己的努力留下足迹 喜欢的话可以点个赞谢谢了。 作者&#xff1…

【全国大学生电子设计竞赛】2024年E题

&#x1f970;&#x1f970;全国大学生电子设计大赛学习资料专栏已开启&#xff0c;限时免费&#xff0c;速速收藏~

快速查找WGS1984 坐标地理坐标系转UTM投影坐标的多种方法

在arcgis中如果是要计算长度或面积&#xff0c;则需要将矢量图层地理坐标系转为投影坐标系&#xff0c;下面总结了几种快速找到“WGS 1984”&#xff08;UTM ZONE&#xff09;投影带号的方法。 一、准备工作 软件&#xff1a;arcmap 示例数据&#xff1a;安微省shp矢量图 二…

删除链表的倒数第N个结点(LeetCode)

题目 给你一个链表&#xff0c;删除链表的倒数第个结点&#xff0c;并且返回链表的头结点。 示例1&#xff1a; 输入&#xff1a;&#xff0c; 输出&#xff1a; 示例2&#xff1a; 输入&#xff1a;&#xff0c; 输出&#xff1a; 示例3&#xff1a; 输入&#xff1a;&#x…

申瓯通信设备有限公司在线录音管理系统(复现过程)

漏洞简介 申瓯通信设备有限公司在线录音管理系统 index.php接口处存在任意文件读取漏洞&#xff0c;恶意攻击者可能利用该漏洞读取服务器上的敏感文件&#xff0c;例如客户记录、财务数据或源代码&#xff0c;导致数据泄露 一.复现过程 fofa搜索语句:title"在线录音管…