数据结构——【堆】

一、堆的相关概念

1.1、堆的概念

1、堆在逻辑上是一颗完全二叉树(类似于一颗满二叉树只缺了右下角)。

2、堆的实现利用的是数组,我们通常会利用动态数组来存放元素,这样可以快速拓容也不会很浪费空间,我们是将这颗完全二叉树用层序遍历的方式储存在数组里的。

3、堆有两种分别是大根堆小根堆 。

1.2、堆的分类

1.2.1、大根堆

大根堆就是整个完全二叉树,任意一个根节点的值都比左右子树的值大    

          

这就是一个大根堆,所有根节点的值永远比左右子树的大,那么就可以看出,整棵树的根节点,他的值是整个堆中最大的。同时我们也发现没有直接父子关系的节点他们的值没有完全地关系,就像第二层的33和第三层的45以及20,没有规定第三层的元素值必须小于第二层,只要满足根节点比自己左右子树节点的值大即可。

1.2.3、小根堆

小根堆表示整个完全二叉树,任意一个根节点的值都比左右子树的值小

            

以上就是一个简单地小根堆它的定义与大根堆相似,只是跟节点的值小于自己的左右节点的值,同时小根堆的层与层之间没有直接关系的节点的值也没有必然的大小关系

1.3、堆的结构

堆的逻辑结构是一颗完全二叉树

堆的物理结构是一个数组

我们可以用左右孩子节点和父节点,来表示所有的节点。

leftchild = parent * 2 + 1;

rightchild = parent * 2 + 2;

parent = (child - 1) / 2;(child可以是左孩子,也可以是右孩子)

 如下图:是一个大根堆,父节点的值都大于子节点的值。

在数组中存储的是:

10865743

二、堆的实现

2.1、堆的功能

我们是以顺序表的形式实现的堆,其中基本的操作和顺序表的操作是大致一样的。

下面是我们要实现的堆的一些基础功能


#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;//堆的初始化
void HeapInit(Heap* hp);
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
//打印堆
void HeapPrint(Heap* hp);
//交换函数
void Swap(HPDataType* p1, HPDataType* p2);

2.2、堆函数的实现

#include"Heap.h"//初始堆
void HeapInit(Heap* hp)
{assert(hp);hp->a = NULL;hp->size = 0;hp->capacity = 0;
}// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp->a);hp->a = NULL;hp->size = hp->capacity = 0;
}//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp = *p1;*p1 = *p2;*p2 = temp;
}//向上调整(前面的是堆)
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){//小堆if (a[child] <  a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}//打印堆
void HeapPrint(Heap* hp)
{assert(hp);for (size_t i = 0; i < hp->size; i++){printf("%d ",hp->a[i]);}printf("\n");
}// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->size == hp->capacity){int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;HPDataType* tem = (HPDataType*)realloc(hp->a,sizeof(HPDataType)*newcapacity);if (tem == NULL){perror("malloc fail");exit(-1);}hp->a = tem;hp->capacity = newcapacity;}hp->a[hp->size] = x;hp->size++;AdjustUp(hp->a, hp->size - 1);
}//向下调整(大堆或者小堆)
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//小堆if (child + 1 < n && 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 HeapPop(Heap* hp)
{assert(hp);assert(hp->size>0);Swap(&hp->a[0], &hp->a[hp->size-1]);--hp->size;AdjustDown(hp->a, hp->size, 0); //大堆
}// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{assert(hp);assert(a);hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (hp->a == NULL){perror("malloc fail");exit(-1);}hp->size = n;hp->capacity = n;memcpy(hp->a, a,sizeof(HPDataType) * n);//建堆for (int i = 1; i < n; i++){AdjustUp(hp->a, i);}
}// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(hp->size > 0);return hp->a[0];
}// 堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);return hp->size == 0;
}// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp->size;
}

2.3、堆的插入

堆是一个完全二叉树,在插入元素时是在堆的末尾插入的,但是为了把一个元素插入后,使这个堆还是一个堆,我们需要对堆中的数据尽心再次调整。

向上调整

我们插入一个元素是,在进行向上调整,把这个数放到合适的位置。我们来看看代码实现

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){//大堆if (a[child] >  a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}

下面这张图帮助大家理解

接下来我们来实现堆的插入

我们还是和顺序表一样,相对其扩容情况进行讨论,当hp->size==hp->capacity时,证明没有多余空间了,我们需要增加空间,这里还是使用,realloc函数,将这个数插入进去后,对这个数进行向上调整,使之变成一个新堆。

void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->size == hp->capacity){int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;HPDataType* tem = (HPDataType*)realloc(hp->a,sizeof(HPDataType)*newcapacity);if (tem == NULL){perror("malloc fail");exit(-1);}hp->a = tem;hp->capacity = newcapacity;}hp->a[hp->size] = x;hp->size++;AdjustUp(hp->a, hp->size - 1);
}

2.4、堆的删除

向上调整

我们在堆中删除一个元素时删除的时堆顶元素,也就是第一个元素,我们一般会先让第一个元素和最后一个元素交换位置,然后hp->size--;为了让新的数据成为堆,我们将第一个数据向下调整,使之变成一个新堆。

我们来看看向下调整的代码该如何写:

void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//小堆if (child + 1 < n && a[child+1] > a[child])   //找到两个孩子节点较大的值{child++;}//建小堆if (a[child]>a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

我们来看看这张图跟好的理解向下调整:

接下来我们来实现堆的删除

我们先考虑一下hp->size的临界问题,用一个断言就可以避免此类问题。

void HeapPop(Heap* hp)
{assert(hp);assert(hp->size>0);Swap(&hp->a[0], &hp->a[hp->size-1]);--hp->size;AdjustDown(hp->a, hp->size, 0); //大堆
}

三、建堆

给一个数组我们如何把这个数组建成堆呢?

一般我们都有两种方法:

3.1、自顶向下(向上调整)

我们来看看代码如何实现

void HeapCreate(Heap* hp, HPDataType* a, int n)
{assert(hp);assert(a);hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (hp->a == NULL){perror("malloc fail");exit(-1);}hp->size = n;hp->capacity = n;memcpy(hp->a, a,sizeof(HPDataType) * n);//建堆for (int i = 1; i < n; i++){AdjustUp(hp->a, i);}
}

我们使用错位相减的方式来计算 自顶向下(向上调整)的时间复杂度

时间复杂度:O(nlog(2)^n)

3.2、自低向上(向下调整)

我们来看看代码如何实现

void HeapCreate(Heap* hp, HPDataType* a, int n)
{assert(hp);assert(a);hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (hp->a == NULL){perror("malloc fail");exit(-1);}hp->size = n;hp->capacity = n;memcpy(hp->a, a,sizeof(HPDataType) * n);//建堆//向下调整算法for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}
}

和自顶向下一样,还是错位相减来计算时间复杂度

时间复杂度:O(n)

四、堆的排序

我们学习堆,有一个很有用的地方,就是可以用堆进行排序,因为我们知道,大堆堆顶元素是数组中最小的,小队堆顶是数组中元素最小的。

当我们需要将一个数组进行从小到大的排序时:

1.将该数组建成一个大堆

2.第一个数和最后一个数交换,然后把交换的那个较大的数不看做堆里面

3.前n-1和数进行向下调整算法,选出大的数放到根节点,再跟倒数第二个交换......

 代码如下:

void HeapSort(int* a,int n)
{int i = 0;//这里用向下调整算法来建堆,因为时间复杂度只有O(N)for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&amp;a[0], &amp;a[end]);AdjustUp(a, end, 0);--end;}
}

时间复杂度:O(Nlog(2)^N)

五、topk问题

我们在做一些编程题会遇到一类问题,就是topk问题

topk问题指的有一组很大的数据,我们需要返回它最大(最小)的前K个元素。

这里我们就可以用堆排序很好的解决此类问题。

这里力扣平台有一个练习题,我们一起来看一看

面试题 17.14. 最小K个数 - 力扣(LeetCode)

思路:我们先建立一个大堆,先把前K个元素建成一个大堆,然后在将剩下的数和堆顶元素进行比较,如过大于堆顶数据,我们就和堆顶元素进行交换,然后将现在的堆顶元素向下调整,前k个数就是这组数据中最小的前K个数。

我们来看看该如何实现:

void Swap(int* p1, int* p2)
{int temp = *p1;*p1 = *p2;*p2 = temp;
}
//向下调整
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//大堆if (child + 1 < n && a[child+1] > a[child])   //找到两个孩子节点较小的值{child++;}//建大堆if (a[child]>a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}int* smallestK(int* arr, int arrSize, int k, int* returnSize)
{if(k==0){*returnSize=0;return NULL;}int *ret=(int*)malloc(sizeof(int)*k);for(int i=0;i<k;i++){ret[i]=arr[i];}//给前k个元素建大堆for(int i=(k-1-1)/2;i>=0;i--){AdjustDown(ret, k, i);}for(int i=k;i<arrSize;i++){if(ret[0]>arr[i]){ret[0]=arr[i];AdjustDown(ret,k,0);}}*returnSize=k;return ret;
}

六、大量数据中的topk问题

比如我们现在有100000个数据,我们要找到最大的10个数据,我们需要改怎么实现,还是利用topk解决,我们先将前100个数据建成一个小堆

//创建一个文件,并且随机生成一些数字
void CreateDataFile(const char* filename, int N)
{FILE* Fin = fopen(filename, "w");if (Fin == NULL){perror("fopen fail");exit(-1);}srand(time(0));for (int i = 0; i < N; i++){fprintf(Fin, "%d ", rand() % 10000);}
}
void PrintTopK(const char* filename, int k)
{assert(filename);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;}//读前k个数for (int i = 0; i < k; i++){//空格和换行默认是多个值之间的间隔fscanf(fout, "%d", &amp;minheap[i]);}//建k个数的堆for (int j = (k - 1 - 1) / 2; j >= 0; j--){AdjustDown(minheap, j, k, cmp_down);}//读取后N-K个int x = 0;while(fscanf(fout,"%d",&amp;x)!=EOF){if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, 0, k, cmp_down);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");free(minheap);fclose(fout);
}
int main()
{//CreateDataFile("data.txt", 1000000);//找前10个最大的数PrintTopK("data.txt", 10);return 0;
}

这里只截取了一小部分

我们提前改10个较大的数,验证返回的正确错误。

返回的就是我们改的10个大的数字,证明返回正确,而且效率极其的高!

总结:堆的知识就介绍到这里,如有疑问或者质疑,请在评论区发出来,我会尽全力帮大家解决,成长的路上少不了你们的支持,你们的三连是我进步最大的动力,还望大佬们多多支持,一起加油!共勉!

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

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

相关文章

【C++】构造函数调用规则 ( 默认构造函数 | 默认无参构造函数 | 默认拷贝构造函数 | 构造函数调用规则说明 )

文章目录 一、默认构造函数1、默认无参构造函数2、默认拷贝构造函数 二、构造函数调用规则1、构造函数规则说明2、代码示例 - 只定义拷贝构造函数3、代码示例 - 只定义有参构造函数 一、默认构造函数 C 类中 2 种特殊的构造函数 , 分别是 : 默认无参构造函数 : 如果 C 类中 没…

PyTorch实现注意力机制及使用方法汇总,附30篇attention论文

还记得鼎鼎大名的《Attention is All You Need》吗&#xff1f;不过我们今天要聊的重点不是transformer&#xff0c;而是注意力机制。 注意力机制最早应用于计算机视觉领域&#xff0c;后来也逐渐在NLP领域广泛应用&#xff0c;它克服了传统的神经网络的的一些局限&#xff0c…

sqlserver存储过程报错:当前事务无法提交,而且无法支持写入日志文件的操作。请回滚该事务。

现象&#xff1a; 系统出现异常&#xff0c;手动执行过程提示如上。 问题排查&#xff1a; 1.直接执行的过程事务挂起&#xff08;排除&#xff09; 2.重启数据库实例&#xff08;重启后无效&#xff09; 3.过程中套用过程&#xff0c;套用的过程中使用事务&#xff0c;因为…

STM32-HAL库06-硬件IIC驱动FM24CL16B非易失存储器

STM32-HAL库06-IIC驱动FM24CL16B非易失存储器 一、所用材料&#xff1a; STM32VGT6自制控制板 STM32CUBEMX&#xff08;HAL库软件&#xff09; MDK5 二、所学内容&#xff1a; 通过HAL库的硬件IIC对FM24CL16B存储器进行写与读取操作。 三、CUBEMX配置&#xff1a; 第一步…

Virtualbox中Ubuntu根目录空间不足

现象 Virtualbox中Ubuntu根目录空间不足 解决 动态存储 虚拟机关闭先在虚拟介质管理里把硬盘Size调大开启Ubuntu用Disks或者GParted重新调整分区大小重新启动 步骤参考: https://zhuanlan.zhihu.com/p/319431032 https://blog.csdn.net/ningmengzhihe/article/details/1272…

Java 毕业设计-基于SpringBoot的在线文档管理系统

基于SpringBoot的在线文档管理系统 博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W,Csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 技术栈简介 文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;sp…

rocketmq

&#x1f353;代码仓库 https://gitee.com/xuhx615/rocket-mqdemo.git &#x1f353;基本概念 ⭐生产者(Producer)&#xff1a;消息发布者⭐主题&#xff08;Topic&#xff09;&#xff1a;topic用于标识同一类业务类型的消息⭐消息队列&#xff08;MessageQueue&#xff09…

VirtualBox宿主机和虚拟机文件互传设置

一、如图1、2、3步骤&#xff0c;设置共享粘贴板和拖放为双向 二、 在启动的虚拟机设置的里面&#xff0c;安装增强插件&#xff0c;然后重启虚拟机。 三、在网络位置就可以看到了

Java基于SpringBoot的闲一品交易平台

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W,Csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 大家好&#xff0c;我是程序员徐师兄、今天给大家谈谈基于android的app开发毕设题目&#xff0c;以及基于an…

学习Bootstrap 5的第八天

目录 加载器 彩色加载器 实例 闪烁加载器 实例 加载器大小 实例 加载器按钮 实例 分页 分页的基本结构 实例 活动状态 实例 禁用状态 实例 分页大小 实例 分页对齐 实例 面包屑&#xff08;Breadcrumbs&#xff09; 实例 加载器 彩色加载器 在 Bootstr…

竞赛 基于情感分析的网络舆情热点分析系统

文章目录 0 前言1 课题背景2 数据处理3 文本情感分析3.1 情感分析-词库搭建3.2 文本情感分析实现3.3 建立情感倾向性分析模型 4 数据可视化工具4.1 django框架介绍4.2 ECharts 5 Django使用echarts进行可视化展示5.1 修改setting.py连接mysql数据库5.2 导入数据5.3 使用echarts…

GeoSOS-FLUS未来土地利用变化情景模拟模型

软件简介 适用场景 GeoSOS-FLUS软件能较好的应用于土地利用变化模拟与未来土地利用情景 的预测和分析中&#xff0c;是进行地理空间模拟、参与空间优化、辅助决策制定的有效工 具。FLUS 模型可直接用于&#xff1a; 城市发展模拟及城市增长边界划定&#xff1b;城市内 部高分…

Debian 12快速安装图解

文章目录 Debian 12安装图解创建虚拟机安装系统登录并用光盘离线安装sudo、curl解决Linux下sudo更改文件权限报错保存快照debain添加在线源(配置清华源)参考 Debian 12安装图解 Debian选择CD安装非常慢&#xff0c;本次安装选择DVD离线安装。 下载 https://www.debian.org/CD…

Swift如何使用Vision来识别获取图片中的文字(OCR),通过SwiftUI视图和终端命令行,以及一系列注意事项

在过去的一年里&#xff0c;我发现苹果系统中的“文字搜图片”功能非常好用&#xff0c;这个功能不光 iPhone/iPad&#xff0c;Mac 也有&#xff0c;找一些图片真的很好用。但是遇到了一个问题&#xff1a;这个功能需要一段时间才能找到新的图片&#xff0c;而且没法手动刷新&a…

从一到无穷大 #15 Gorilla,论黄金26H与时序数据库缓存系统的可行性

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 本作品 (李兆龙 博文, 由 李兆龙 创作)&#xff0c;由 李兆龙 确认&#xff0c;转载请注明版权。 引言 缓存系统的高效存在前提&#xff0c;在满足前提的情况下可以接受缺陷便没有理由不引入缓…

pdf添加水印

给pdf文件添加水印 引入依赖 <dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.5.13.3</version></dependency>添加水印 package com.it2.pdfdemo02.util;import com.itextpdf.tex…

Qt应用程序连接达梦数据库-飞腾PC麒麟V10

目录 前言1 安装ODBC1.1 下载unixODBC源码1.2 编译安装1.4 测试 2 编译QODBC2.1 修改 qsqldriverbase.pri 文件2.2 修改 odbc.pro 文件2.3 编译并安装QODBC 3 Qt应用程序连接达梦数据库测试4 优化ODBC配置&#xff0c;方便程序部署4.1 修改pro文件&#xff0c;增加DESTDIR 变量…

高可用Kuberbetes部署Prometheus + Grafana

概述 阅读官方文档部署部署Prometheus Grafana GitHub - prometheus-operator/kube-prometheus at release-0.10 环境 步骤 下周官方github仓库 git clone https://github.com/prometheus-operator/kube-prometheus.git git checkout release-0.10 进入工作目录 cd kube…

聚观早报|华为Mate 60 Pro支持面容支付;特斯拉重回底特律车展

【聚观365】9月8日消息 华为Mate 60 Pro已支持面容支付 特斯拉将重回底特律车展 iPhone在美国有1.67亿用户 韩国半导体8月份出口85.6亿美元 比亚迪元PLUS冠军版将于9月15日上市 华为Mate 60 Pro已支持面容支付 毫无预热的华为Mate 60 Pro突然在华为商城首批开售&#xf…

老站长带你全面认识基站和天线

认识基站 作为数量最多的移动通信设备 基站几乎是随处可见 其实 基站也分为很多种 基站的天线&#xff0c;也分为很多种&#xff0c;真正都能区分清楚的人其实不多。 什么是基站 Base Station 一般特指“公用移动通信基站” 大家都知道&#xff0c;基站就是给手机提供信…