【数据结构】长篇详解堆,堆的向上/向下调整算法,堆排序及TopK问题

文章目录

  • 堆的概念
      • 性质
      • 图解
  • 向上调整算法
      • 算法分析
      • 代码整体实现
  • 向下调整算法
      • 算法分析
      • 整体代码实现
  • 堆的接口实现
      • 初始化堆
      • 销毁堆
      • 插入元素
      • 删除元素
      • 打印元素
      • 判断是否为空
      • 取首元素
      • 实现堆
  • 堆排序
      • 创建堆
      • 调整堆
      • 整合步骤
  • TopK问题

堆的概念

堆就是将一组数据所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足树中每一个父亲节点都要大于其子节点称为大堆(树中每一个父亲节点都要大于其子节点称为小堆)。

性质

①对于大堆(大根堆)来说,堆的顶部也就是数组首元素一定是最大的元素
②对于小堆(小根堆)来说,堆的顶部也就是数组首元素一定是最小的元素
(这两点对于下面的堆排序来说十分重要)

此外,堆总是一棵完全二叉树,因为堆本身就是二叉树的一种顺序存储结构的实现模式
注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段

图解

在这里插入图片描述

在这里插入图片描述
通过图再去对比上面的概念和性质,理解会更加清晰

所谓的存储结构也就数据在内存中真实的存储情况,在一维数组中
逻辑结构就是我们想象出来的,能够帮助我们理解并且通过这个也是根据二叉树中父节点和子节点之间的下标关系来确定的

①已知父亲节点求子节点

LeftChild = Parent * 2 + 1; //左孩子的节点下标
RightChild = Parent * 2 + 2; //右孩子的节点下标

②已知子节点求父节点

Parent = (Child - 1) / 2;  //切记是减1之后再除以2

向上调整算法

向上调整算法主要在堆的插入堆排序中应用最为广泛

算法分析

对于堆的插入,就是在数组的末尾进行数字的插入,并且在插入数据之后,我们仍要保证现有的结构仍然是一个!
在这里插入图片描述
如上图,是一个小堆

然后在数组的末尾插入了一个数字,即最后一个孩子节点,但是在插入之后,我们自身的堆结构发生了变化,所以我们必须对堆的结构进行调整.

不难发现,在最后插入一个数之后,其他子树仍然保持了小堆的性质(即父节点的值小于子节点),而正在需要调整的就是该子节点的’祖宗’这条线路,如上图红色箭头一步一步指向的位置,
而利用的公式就是Parent = (Child - 1) / 2;把新插入的数和它的父节点作比较,如果这个新插入的数小于于父节点,那么就和父节点交换位置

在向上调整代码中,我们需要传入的参数是数组和插入的那个子孩子的节点的下标

void AdjustUp(HeapDataType* a, int child)  //child是下标

在实际的不断向上调整中,我们需要用循环来实现代码,并且要合理的设置循环

while (child > 0)   //不能设置为parent >= 0 {				//Parent = (Child - 1) / 2, 通过这个公式因为parent永远都不可能小于零...}

时间复杂度 -------O(logN)

根据最坏情况来看(比如上图),数据多少层,我们就需要调整多少次,所以次数=高度h
再根据二叉树节点数量和高度的关系可知:
在这里插入图片描述
所以可以得到关系: 次数 = h = logN
所以时间复杂度就为:O(logN)

代码整体实现

算法既可以实现小堆也可以大堆,具体看你函数内部符号的控制

整体实现如下:

typedef struct HeapNode
{HeapDataType* a;int size;int capacity;
}HP;
void Swap(HeapDataType* p1, HeapDataType* p2)
{HeapDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//循环写法
void AdjustUp(HeapDataType* a, int child)  //child,parent是下标
{int parent = (child - 1) / 2;while (child > 0){//小堆:判断子节点和父亲结点的大小if (a[child] < a[parent])//大堆:if (a[child] > a[parent]){Swap(&a[child], &a[parent]);//交换孩子和父亲child = parent;parent = (child - 1) / 2;}else{break;}}
}//递归写法
void AdjustUp(HeapDataType* a, int child)
{int parent = (child - 1) / 2;if (child > 0){//小堆:if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;AdjustUp(a, child);  //递归}else{return;}}else{return;}
}

向下调整算法

向上调整算法主要在堆的数据删除堆排序中应用最为广泛

算法分析

在这里插入图片描述
对于上图根节点27来说,它的左右子树都是小堆,所以就需要将27不断向下调整,保证其整体还是一个小堆
由此可见,向下调整的前提是左右子树必须是堆
利用的公式就是
LeftChild = Parent * 2 + 1;
RightChild = Parent * 2 + 2;

在每一轮的调整中你都需要比较左右子节点的大小,比如上图就是对于27来说,15和17两个节点,15更小,所以就将15和27进行交换,然后对于19这个子树来说本身就是一个小堆,就可以不用管了,并且15本身也小于19,所以也符合小堆性质,然后继续对左边的子树进行如此的调整

在向下调整代码中,我们需要传入的参数是数组,数组大小和整棵树根节点的下标

void AdjustDown(HeapDataType* a, int size, int parent)

时间复杂度 -------O(logN)

根据最坏情况来看(比如上图),数据多少层,最坏的情况我们就需要向下调整多少次,所以次数=高度h, 再根据二叉树节点数量和高度的关系可知:
在这里插入图片描述
所以可以得到关系: 次数 = h = logN
所以时间复杂度就为:O(logN)

整体代码实现

typedef int HeapDataType;typedef struct HeapNode
{HeapDataType* a;int size;int capacity;
}HP;
//转换
void Swap(HeapDataType* p1, HeapDataType* p2)
{HeapDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//循环写法
void AdjustDown(HeapDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size)//这里的child是左孩子下标,之所以不是child+1<size,是因为{			        //如果没有右孩子的话,这次循环将会终止,调整就会进行不彻底//小堆:if (child + 1 < size && a[child + 1] < a[child]){child++;}//小堆:if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;//交换位置}else{break;}}
}
//递归写法
void AdjustDown(HeapDataType* a, int size, int parent)
{int child = parent * 2 + 1;if (child < size) {//小堆:if (child + 1 < size && a[child + 1] < a[child]){child++; //如果右孩子小,那么下标就换成右孩子的下标}//小堆:if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;AdjustDown(a, size, parent);  //递归}else{return;}}else{return;}
}

堆的接口实现

接下里,我将把堆的实现过程一步一步实现出来

初始化堆

void HeapInit(HP* hp)
{assert(hp);hp->a = NULL;hp->size = 0;hp->capacity = 0;
}

销毁堆

void HeapDestroy(HP* hp)
{assert(hp);free(hp->a);hp->a = NULL;hp->size = hp->capacity = 0;
}

插入元素

在尾部插入之后,要用AdjustUp函数向上调整形成堆

void HeapPush(HP* hp, HPDataType x)
{assert(hp);// 扩容if (hp->size == hp->capacity){int new = hp->capacity == 0 ? 4 : hp->capacity * 2;HPDataType*tmp=(HPDataType*)realloc(hp->a, sizeof(HPDataType) * new);if (tmp == NULL){perror("realloc fail");exit(-1);}hp->a = tmp;hp->capacity = new;}hp->a[hp->size] = x;hp->size++;AdjustUp(hp->a, hp->size - 1);//插入之后向上调整堆
}

删除元素

一般指删除首元素,至于为什么HeapPop是删除首元素
根本就是因为要弹出尾元素很简单,直接size–不就完了

void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);//首元素换到尾部来,然后再size----php->size;AdjustDown(php->a, php->size, 0);//再用AdjustDown函数再来调整堆
}

打印元素

void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

判断是否为空


bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

取首元素

HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

实现堆

int main()
{HP hp;HeapInit(&hp);int a[] = { 20, 11, 28, 31, 111, 52, 34, 16, 7, 9 };for (int i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);//插入}HeapPop(&hp);//把堆的首元素7删除删除HeapPrint(&hp);printf("堆顶元素:%d\n", HeapTop(&hp));HeapDestroy(&hp);return 0;
}

运行出来的结果:
在这里插入图片描述

堆排序

首先堆排有几个关键的步骤
①创建堆 ②调整堆

创建堆

创建堆的方式有两种①向上调整建堆 ②向下调整建堆

①首先我们来看第一种:向上调整建堆

这种方式的原理就是看作最开始堆中只有一个元素,从第一个元素开始就已经在向上调整,然后逐渐像堆中加入元素,随着一个一个元素的加入,也就形成了堆
图解如下:
在这里插入图片描述
而代码就是通过AdjustUp函数和一个for循环就可以完成上面步骤

//以前n个数建小堆
for (int i = 0; i < n; ++i)
{AdjustUp(a, i);  //a为数组的指针
}

时间复杂度: O(n*logn)

分析:首先我们上面详细分析了AdjustUp()的时间复杂度为O(logn),然后循环了n此每次建堆,所以两者相乘,时间复杂度也就是 n*logn


②我们来看第一种:向下调整建堆 -----堆排序中最主要用到的方法

这种建堆的关键就是从倒数第一个非叶子节点开始调(也就是树中最后一个父节点),然后逐渐+1,就可以调整从最后一个父节点开始的每一棵树.
不难发现这样也符合向下调整的前提,即左右子树都是堆
那么我们如何找到最后一个节点的父亲?
就需要用到公式:Parent = (Child - 1) / 2;
图解如下
在这里插入图片描述

而代码就是通过AdjustDown函数和一个for循环就可以完成上面步骤

for (int i = ((n-1)-1)/2; i >= 0; --i) 
//(n-1)是拿到树最后一个节点,然后再根据公式Parent = (Child - 1) / 2;
{AdjustDown(a, size, i);
}

时间复杂度:O(n)
根据下面的思路
在这里插入图片描述
在这里插入图片描述

因此建堆的时间复杂度为O(n)

总结😗:其实两种方式建堆之所以时间复杂度有差距,就是因为向下调整建堆可以看作忽略了最后一排的节点,直接从倒数第二排节点开始调整的,而在一棵满二叉树中最后一排的节点其实就占据了整棵树的二分之一,所以相当于向下调整比向上调整少经历了很多的节点
所以实际堆排序中我们更多的使用的是向下调整建堆,因此时间复杂度为O(n)

还有一点需要注意的是:如果你想要升序,即从小打大,需要建大堆.
建了大堆之后,再交换首元素(最大的)和末尾元素,然后把最大的元素不算入堆中的元素,
再进行向下调整
如果你建小堆,当你拿到首元素(最小的元素之后),需要将数组依次前移然后重新建堆,每次都前移然后每次都建堆,时间复杂度直接拉满!!!
同理 如果你想要降序,即从大打小,需要建小堆.


调整堆

在堆建好之后,就可以开始调整堆了,比如你是升序,即从小打大,需要建大堆.
建了大堆之后,循环N次 ,进行N次调整堆操作,每一次调整 堆得到的最大值,将此值和数组的最后一个元素进行交换,交换减小数组的长度(最后被减小的那几个值不参与堆的调整),直到最后一个元素,就完成了堆的排序.

如下图,降序—小堆, 展示了其中一个调整过程

在这里插入图片描述

整合步骤

综合建堆和调整,完整的堆排序代码就出来了

void HeapSort(int* a, int n)
{// 建堆 (大堆)or  (小堆)for (int i = 1; i < n; i++){AdjustUp(a, i);}
int end = n - 1;
while (end > 0)
{Swap(&a[0], &a[end]);  //交换AdjustDown(a, end, 0); //向下调整--end;   //换下来的最后一个数不计入堆中
}

升序建大堆,降序建小堆很重要!

TopK问题

最后我们再来解决一个堆在实际应用中很重要的Topk问题

通常这是在数据很大的情况下才会使用到的,如世界前500强,全省高考前十等等…
因为如果数据很大,你不可能在内存中创建一个这么大的数组来装下这么多数据,所以就要用topk问题的思路
举个简单的例子:
比如你有1000个数据,你要找前100个大的数据,那么你先随便拿100个数据(无论其大小多少)建小堆,然后另外900个数据依次与堆顶的最小数据进行比较,比它大就替换,然后再调整堆,这样1000个数据都参与了对比,对比了900次,900个最小的被拿走,剩下的100个一定是最大的,再进行堆排序

接下来用文件传输数据的形式进行举例

void CreateNDate()
{// 造数据int n = 10000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void TestTopK(const char* filename, int k)
{// 1. 建堆--用a中前k个元素建堆FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc fail");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 前k个数建小堆for (int i = (k-2)/2; i >=0 ; --i){AdjustDown(minheap, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minheap[0]){// 替换你进堆minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");fclose(fout);
}int main()
{CreateNDate();TestTopK("data.txt", 5);return 0;
}

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

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

相关文章

记录一次Docker与Redis冲突

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 报错以及Bug ✨特色专栏&#xff1a; …

避坑之路 —— 前后端 json 的注意问题

当我们在进行开发项目的时候&#xff0c;在前后端需要进行数据之间的传输&#xff0c;那么就会需要到json。而json算是字符串中的一种 1.先说一下前端的, 其实这两种都是表示前端希望能收到后端json这样的数据格式&#xff0c;那么我们在后端就需要注意将数据进行转换为json进…

深度学习模型复杂度分析大杂烩

深度学习模型复杂度分析大杂烩 时间复杂度和空间复杂度是衡量一个算法的两个重要指标,用于表示算法的最差状态所需的时间增长量和所需辅助空间. 在深度学习神经网络模型中我们也通过&#xff1a; 计算量/FLOPS&#xff08;时间复杂度&#xff09;即模型的运算次数 访存量/By…

数据结构与算法基础-学习-34-基数排序(桶排序)

目录 一、基本思想 二、算法思路 1、个位排序 &#xff08;1&#xff09;分配 &#xff08;2&#xff09;收集 2、十分位排序 &#xff08;1&#xff09;分配 &#xff08;2&#xff09;收集 三、源码分享 1、InitMyBucket 2、DestroyMyBucket 3、ClearMyBucket 4、…

软件测试/测试开发丨使用ChatGPT自动进行需求分析

简介 在实际工作过程中&#xff0c;常常需要拿到产品的PRD文档或者原型图进行需求分析&#xff0c;为产品的功能设计和优化提供建议。 而使用ChatGPT可以很好地帮助分析和整理用户需求。 实践演练 接下来&#xff0c;需要使用ChatGPT 辅助我们完成需求分析的任务 注意&…

【论文笔记】Baidu Apollo EM Motion Planner

文章目录 AbstractI. INTRODUCTIONA. Multilane StrategyB. Path-Speed Iterative AlgorithmC. Decisions and Traffic Regulations II. EM PLANNER FRAMEWORK WITH MULTILANE STRATEGYIII. EM PLANNER AT LANE LEVELA. SL and ST Mapping (E-step)B. M-Step DP PathC. M-Step …

01-Redis核心数据结构与高性能原理

上一篇&#xff1a; 1.Redis安装 下载地址&#xff1a;http://redis.io/download 安装步骤&#xff1a; # 安装gcc yum install gcc# 把下载好的redis-5.0.3.tar.gz放在/usr/local文件夹下&#xff0c;并解压 wget http://download.redis.io/releases/redis-5.0.3.tar.gz…

【ArcGIS Pro二次开发】(67):处理面要素空洞

这个一个简单的小功能。 有些面要素可能会存在空洞&#xff0c;这个工具的目的就是获取面要素的空洞&#xff0c;或者去除空洞获取要素的边界。 这个功能其实在之前做拓扑功能的时候就已经有了&#xff0c;这次只是单独把它提取出来。因为有时候会单独用到这个功能。 一、要实…

面试半个月后的一些想法

源于半个月面试经历后的一些想法&#xff0c;刚开始想的是随便写写&#xff0c;没想到居然写了这么多。 找不到目标找不到意义亦或是烦躁的时候&#xff0c;就写写文章吧&#xff0c;把那些困扰你很久的问题铺开来 花时间仔细想想&#xff0c;其实真正让我们生气懊恼&#xff0…

JS中应该注意的点

本帖子记录在使用前端时遇到的一些小点。 1.html()和text()和val()的使用及区别 1.1 val() val&#xff08;&#xff09;是对于单标签元素的值&#xff0c;其中一个很重要的特性是value"" Value:<input id"input" type"text" value"LO…

MySQL高可用搭建方案之(MMM)

有的时候博客内容会有变动&#xff0c;首发博客是最新的&#xff0c;其他博客地址可能会未同步,认准https://blog.zysicyj.top 注意&#xff1a;这篇转载文章&#xff0c;非原创 首发博客地址 原文地址 前言 MySQL的高可用有很多种&#xff0c;有我们经常说的MMM架构、MHA架构、…

TGA格式文件转材质

今天淘宝上买了一个美女的模型&#xff0c;是blender的源文件&#xff0c;上面说有fbx格式的。我用unity&#xff0c;所以觉得应该可以用。文件内容如下图&#xff1a; FBX文件夹打开后&#xff0c;内容如下图所示&#xff0c;当时就预感到可能没有色彩。 unity打开后果然发现只…

笔记本选购指南

大学生笔记本电脑选购指南 文章目录 笔记本分类指标排行 了解自身需求理工科文科艺术总结 参考指标品牌CPU显卡屏幕其他 购买渠道推荐游戏本Redmi G 锐龙版联想G5000惠普光影精灵9天选4锐龙版联想R7000P暗影精灵9联想拯救者R9000P 全能本华硕无畏PRO15联想小新Pro14 2023 轻薄本…

『SpringBoot 源码分析』run() 方法执行流程:(3)刷新应用上下文-处理 @ComponentScan 注解

『SpringBoot 源码分析』run() 方法执行流程&#xff1a;&#xff08;3&#xff09;刷新应用上下文-处理 ComponentScan 注解 基于 2.2.9.RELEASE问题&#xff1a;当方法进行了注释标记之后&#xff0c;springboot 又是怎么注入到容器中并创建类呢&#xff1f; 首先创建测试主…

论文笔记:Deep Representation Learning for Trajectory Similarity Computation

ICDE 2018 1 intro 1.1 背景 用于计算轨迹相似性的成对点匹配方法&#xff08;DTW&#xff0c;LCSS&#xff0c;EDR&#xff0c;ERP&#xff09;的问题&#xff1a; 轨迹的采样率不均匀 如果两个轨迹表示相同的基本路径&#xff0c;但是以不同的采样率生成&#xff0c;那么这…

如何用Jmeter编写脚本压测

随着商业业务不断扩张&#xff0c;调用adsearch服务频率越来越高&#xff0c;所以这次想做个压测&#xff0c;了解目前多少并发量可以到达adsearch服务的界值。 这次选用的jmeter压测工具&#xff0c;压测思路如图&#xff1a; 同时&#xff0c;我也准备了一份软件测试面试视频…

基于Dlib+PyQt5+TensorFlow智能口红色号检测推荐系统——深度学习算法应用(含Python全部工程源码及模型)+数据集

目录 前言总体设计系统整体结构图系统流程图 运行环境Python环境TensorFlow环境安装face_ recognition安装colorsys模块安装PyQt 5安装QCandyUi库依赖关系 模块实现1. 数据预处理1&#xff09;源数据的存储2&#xff09;处理数据3&#xff09;合并得到json文件 2. 系统搭建1&am…

计算机竞赛 大数据商城人流数据分析与可视化 - python 大数据分析

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于大数据的基站数据分析与可视化 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度…

无涯教程-JavaScript - FVSCHEDULE函数

描述 FVSCHEDULE函数在应用一系列复合利率后返回初始本金的未来值。使用FVSCHEDULE以可变或可调汇率计算投资的未来价值。 语法 FVSCHEDULE (principal, schedule)争论 Argument描述Required/OptionalPrincipalThe present value.RequiredScheduleAn array of interest rat…

Android T 窗口层级其三 —— 层级结构树添加窗口

文章目录 序节点添加Task以DefaultTaskDisplayArea为父节点以Task为父节点 ActivityRecordWindowTokenWindowState以WindowToken为父节点以ActivityRecord为父节点 小结调用场景添加差异 流程分析添加log堆栈打印流程LauncherStatusBar 序 尚未添加窗口的层级结构树&#xff0…