堆的结构实现与应用

目录

         前言:

1.认识堆

a.如何认识堆?

b.大根堆与小根堆

c.堆应用的简单认识

2.堆的结构与要实现的功能

3.向上调整算法

4.向下调整算法

5.向堆插入数据并建堆

6.堆的大小

7.堆的判空

8.取堆顶数据

9.删除堆顶数据

10.向上调整时间复杂度

11.向下调整时间复杂度

12.堆排序

a.直接将数组放到堆再取堆顶

b.在将数组放到堆的时候就直接调整,用数组建堆

13.topk问题

总结:


前言:

堆其实与二叉树息息相关,本篇将从如何实现堆,以及堆的应用等方面入手。

1.认识堆

a.如何认识堆?

我们只要记住关键的两点:1.堆必须是完全二叉树。2.堆要么是大堆,要么是小堆。

b.大根堆与小根堆

那什么是大堆,什么又是小堆呢?

大堆:树中任意一个父亲都大于或等于孩子。

小堆:树中任意一个父亲都小于或等于孩子。

c.堆应用的简单认识

堆排序:时间复杂度为O(N*logN),属于快一点的排序。

topk问题:N个数找最大的前K个。

优先级队列:C++中stl的priority_queue容器的底层实现需要用到建堆的思想。

2.堆的结构与要实现的功能

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;HPDataType size;HPDataType capacity;
}HP;void InitHeap(HP* php);
void DestroyHeap(HP* php);
void PushHeap(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(int* a, int n, int parent);
void Swap(HPDataType* p1, HPDataType* p2);

我们提供以下数据来建堆:

3.向上调整算法

我们现在如果要让提供的数据插入到这个堆里面,如何保证插入的时候就建好堆了呢?这时我们就要用到向上向下调整的算法了。假设我们现在要建一个小堆,就要保证每一个子节点都要小于或者等于它的父节点,用我们提供好的数据,当插入到32这个数据的时候就要进行调整了:

既然是向上调整,那我们就要找孩子的父亲,那如何找到父亲呢?通过下标的关系可以发现,不管是左还是右孩子,只要遵循(child-1)/2就能找到父亲的下标,然后就是交换嘛;交换过后我们要让孩子走到父亲位置,再找到新的父亲,一轮一轮的向上,这就是向上调整算法:

void AdjustUp(HPDataType* a, int child)
{//默认建小堆int parent = (child - 1) / 2;while (child > 0)//等于0就停止了,等于0说明孩子在根的位置,就没有父亲了{if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;//孩子走到父亲的位置继续再找新的父亲parent = (child - 1) / 2;}else{break;}}

要注意的就是循环条件,如果孩子走到0说明走到根的位置了,就没有父亲了,循环停止。

4.向下调整算法

向下调整算法与向上调整算法相反,其实向下就是找孩子,如果建小堆就让左右孩子中最小的孩子与父亲交换(最小的孩子与父亲交换后,父亲就变成三者中最小的了,符合小堆的性质),再让父亲走到孩子的位置上,再往下继续找到新的孩子,直到孩子不存在的情况。

关键来了,如何找到左右孩子中的最小的那个呢?如何通过父亲找到孩子呢?

我们可以默认左孩子是最小的那一个,如果左孩子大于右孩子,那做孩子的下标+1不就到右孩子了吗?解决了第一个问题,那如何通过父亲找到孩子呢,既然我们默认左孩子是小的那一个,我们可以先找到左孩子,通过下标的关系,我们就知道左孩子child=parent*2+1,好了,这就是向下调整算法的思路,来看代码:

void AdjustDown(int* a, int n, int parent)
{//默认小堆int child = parent * 2 + 1;//默认是左孩子while (child < n){//这里右孩子的存在条件必须放在&&的前面,因为如果放在后面,前面的条件为假,右孩子也为假,就判断不出来是哪个了(检查右孩子存在必须更严格)if (child + 1 < n && a[child] > a[child + 1])//如果右孩子存在(因为如果左孩子为n-1,那右孩子就为n了,就越界了)并且左孩子大于右孩子,下标就走到右孩子上{child = child + 1;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}

注意点:

1.我们既然默认左孩子为小的那一个,那结束条件就应该是左孩子不存在的情况即当左孩子等于n的时候就越界了,而又由于堆是完全二叉树,所以左孩子不存在,那右孩子一定不存在,所以只写这一个就行。

2.child + 1 < n && a[child] > a[child + 1],首先需要注意左孩子存在,但右孩子不存在的情况,所以判断child+1<n,其次这个条件要写到&&的前面,因为如果写到后面,a[child]>a[child+1]为假,就判断不出右孩子可能越界的情况了,所以右孩子的检查应该放到&&前面。

5.向堆插入数据并建堆

void PushHeap(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int NewCapacity = php->capacity = 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * NewCapacity);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = NewCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//向上调整传孩子,即插入的数据,找父亲}

需要注意的是最后向上调整传的孩子是插入的数据的下标,因为插入后size++了,所以-1才对应插入的数据的下标。

6.堆的大小

int HeapSize(HP* php)
{assert(php);return php->size;
}

7.堆的判空

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

8.取堆顶数据

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

9.删除堆顶数据

如果我们直接删除堆顶的数据会导致这个堆变乱,所以我们采用交换堆顶和堆尾的数据,将堆的大小减1,这样就访问不到堆尾的数据也就起到了删除的效果了,然后我们再从根节点开始做向下调整算法,恢复堆即可,注意空堆不能删,要判空:

void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(&php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);//从根节点开始向下调整}

10.向上调整时间复杂度

按最坏的情况计算时间复杂度,就拿满二叉树来说:

我们先找到每一次的节点数,再乘向上调整的次数,假设树的高度为h,那我们就将1-h层的所有节点的调整次数相加,就是时间复杂度(计算采用等比数列求和的乘公比错位相减的方法):

又因为满二叉树的节点个数为2^h-1,所以我们设树有N个节点,就能得到高度,再代入F(h):

实际去除不影响结果的项也就是O(N*logN),N为节点个数。

11.向下调整时间复杂度

一样拿满二叉树来说:

实际计算结果:

实际去除不影响结果的项也就是O(N),N为节点个数。

12.堆排序

a.直接将数组放到堆再取堆顶

void HeapSort1(int* a, int n)
{HP hp;InitHeap(&hp);for (int i = 0; i < n; i++){PushHeap(&hp, a[i]);}int i = 0;while (!HeapEmpty(&hp)){int top = HeapTop(&hp);a[i++] = top;HeapPop(&hp);}
}

这样的坏处就是想要改升序降序要改向上向下调整的逻辑,有些麻烦,而且时间上有些麻烦,需要堆排的时候还要写一个堆出来。

b.在将数组放到堆的时候就直接调整,用数组建堆

如果我们要排成降序,就建小堆,小堆选出最小的,首尾交换,最小的放到最后的位置,最后一个数据不看做堆里面的,再次向下调整就可以选出次小的,以此类推,相当于一个一个头插;

调用一次是O(logN),N次就是O(N*logN),计算方法跟向下调整差不多;

向下调整建堆需要倒着调整,叶子节点不需要处理,倒数第一个非叶子节点即最后一个节点的父亲开始调整:

void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

如果我们要排升序,只需要改动向下调整或者写两个建堆方法:

改动两处:选孩子时选大的那个;如果孩子大于父亲,交换:

建堆时也可向上调整建堆,具体实现博主暂时不清楚~~~:

for (int i = 1; i < n; i++)//下标为0即第一个数默认是堆{AdjustUp(a, i);//建堆,相当于一个一个插入成堆}

注意:

1.为什么升序不建小堆呢?因为小堆最小的已经在前面了,不管是移动还是怎么剩下的都要重新建堆

2.堆排序整体时间复杂度为N+N*logN,也就是O(N*logN)

13.topk问题

什么是topk问题?

就是N个数找最大的前N个:

面对庞大的数据,数据放在磁盘的文件里面,而内存是有限的,所以我们将这些数据的前k个建堆,将剩下的数据与堆顶元素进行比较,符合条件就交换,然后再调整,重复操作即可,那该怎么建堆呢?首先对前3 数据进行建一个小堆,注意这里不能建大堆,如果建大堆的话,可能最大的数据在前三个数,其余2个数据在余下的 N-K个数里面,这样其余2个就不能进堆了:

void CreateNData()
{//造数据int n = 10000;srand((unsigned int)time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; i++){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void PrintTopK(int k)
{const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}int val = 0;while (!feof(fout))//fscanf读到文件结尾,调用feof,feof读到文件末尾返回非0,否则返回0{fscanf(fout, "%d", &val);if (val > kminheap[0]){kminheap[0] = val;AdjustDown(kminheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");
}

总结:

堆的结构不难,难在和其他的场景联系到一起并涉及一些算法,所以还是掌握好它结构和算法的基础为主

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

汇总利用YOLO8训练遇到的报错和解决方案(包含训练过程中验证阶段报错、精度报错、损失为Nan、不打印GFLOPs)

一、本文介绍 本文为专栏内读者和我个人在训练YOLOv8时遇到的各种错误解决方案&#xff0c;你遇到的问题本文基本上都能够解决&#xff0c;同时本文的内容为持续更新&#xff0c;定期汇总大家遇到的问题已经一些常见的问题答案&#xff0c;目前包含的问题已经解决方法汇总如下…

“替代云”知多少?Akamai Linode 重新定义公有云服务!

自2006年云计算概念提出以来&#xff0c;云产业已经成为数字化时代所必备的底层基础&#xff0c;但随着多元化的业务需求的增多&#xff0c;多云战略、本地部署所形成混合环境&#xff0c;都使得云复杂性&#xff0c;日渐成为了迫在眉睫的挑战。 451 Research 云价格指数 (CPI…

前端基础自学整理|HTML + JavaScript + DOM事件

目录 一、HTML 1、Html标签 2、Html元素 3、基本的HTML标签 二、CSS 样式 层叠样式表 三、JavaScript 使用示例 四、HTML DOM 通过可编程的对象模型&#xff0c;javaScript可以&#xff1a; window document 1、查找HTML元素 2、操作HTML元素 获取元素的属性 四…

Linux---进程间通讯(上)

一、进程间通讯的目的 数据传输&#xff1a;一个进程需要将它的数据发送给另一个进程资源共享&#xff1a;多个进程之间共享同样的资源。通知事件&#xff1a;一个进程需要向另一个或一组进程发送消息&#xff0c;通知它&#xff08;它们&#xff09;发生了某种事件&#xff0…

聚观早报 | OPPO公布全新AI战略;华为P70 Art影像细节曝光

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 2月22日消息 OPPO公布全新AI战略 华为P70 Art影像细节曝光 苹果正加速开发智能戒指 微软将大规模投资人工智能 …

ArcgisForJS如何访问Arcgis Server?

文章目录 0.引言1.准备ArcGIS相关工具2.创建含有ArcSDE地理数据库的MXD文件3.注册ArcSDE地理数据库4.发布数据到Arcgis Server5.ArcgisForJS访问ArcGIS Server数据 0.引言 ArcGIS API for JavaScript 是一个用于在Web和移动应用程序中创建交互式地图和地理空间分析应用的库。它…

[word] 如何使用Excel制作简单的流程图 #媒体#微信#学习方法

如何使用Excel制作简单的流程图 对于在职场办公的朋友们来说&#xff0c;经常要使用到Excel演示公式&#xff0c;制作各种图表等等&#xff0c;其实Excel还可以制作简单的流程图呢&#xff0c;估计许多小伙伴们还不知道吧&#xff0c;今天就来给大家演示一下&#xff0c;看完就…

在VSCode中新配置一个ros项目

如何从零开始配置一个ros项目 预先准备初始化ros工程运行hello_ros进行第一个示例进行编译测试 预先准备 首先要在vscode中安装&#xff08;必须安装的&#xff09;&#xff1a;ros&#xff0c;c&#xff0c;cmake&#xff0c;cmake tools&#xff08;补全camkelist文件&#…

一个C#开发的大小只有8KB的贪吃蛇开源游戏!

大家好&#xff0c;我是编程乐趣。 今天给大家推荐基于C#开发的、一个贪吃蛇开源项目&#xff0c;这个项目除了实现贪吃蛇的功能外&#xff0c;重点是讲解如何把编译后的程序&#xff0c;从65MB精简为8KB。 项目地址 https://github.com/MichalStrehovsky/SeeSharpSnake 编译…

openssl3.2 - 编译 - zlib.dll不要使用绝对路径

文章目录 openssl3.2 - 编译 - 编译时的动态库zlib.dll不要使用绝对路径概述测试zlib特性在安装好的目录中是否正常笔记70-test_tls13certcomp.t80-test_cms.t对测试环境的猜测从头再编译测试安装一次测试一下随便改变位置的openssl用到zlib时是否好使测试一下随便改变位置的op…

为全志D1开发板移植LVGL日历控件和显示天气

利用TCP封装HTTP包请求天气信息 Linux还真是逐步熟悉中&#xff0c;现在才了解到Linux即没有原生的GUI&#xff0c;也没有应用层协议栈&#xff0c;所以要实现HTTP应用&#xff0c;必须利用TCP然后自己封装HTTP数据包。本篇即记录封装HTTP数据包&#xff0c;到心知天气请求天气…

javaSE多态

文章目录 斜体样式1.1 面向对象三大特征 ?1.2 什么是多态 ?*斜体样式*1.3 多态的前提1.4 多态的成员访问特点1.5 多态的优缺点1.6 多态的转型1.7 多态的转型注意1.8 解决转型安全隐患 2 内部类2.1 内部类的分类什么是内部类 ?什么时候使用内部类 ?内部类分类 ? 2.2 成员内…

【医学大模型】大模型 + 长期慢病的预测和管理

大模型 长期慢病的预测和管理 提出背景长期慢病框架慢性疾病检测框架如何实现多提示工程为什么使用多提示 慢性疾病管理框架个性化提示工程医学知识注入 提出背景 论文&#xff1a;https://arxiv.org/abs/2401.12988 慢性疾病是指那些需要长期管理和治疗的疾病&#xff0c;包…

PyTorch深度学习实战(37)——CycleGAN详解与实现

PyTorch深度学习实战&#xff08;37&#xff09;——CycleGAN详解与实现 0. 前言1. CycleGAN 基本原理2. CycleGAN 模型分析3. 实现 CycleGAN小结系列链接 0. 前言 CycleGAN 是一种用于图像转换的生成对抗网络(Generative Adversarial Network, GAN)&#xff0c;可以在不需要配…

车灯裂了用什么胶修复?

当车灯出现裂缝、破口、缺损、裂痕、破裂、破损、崩角、掉角等问题时&#xff0c;可以使用车灯无痕修复专用UV胶进行修复。车灯无痕修复专用UV胶是一种经过处理的UV树脂胶&#xff0c;主要成份是改性丙烯酸UV树脂。应用在车灯的专业无痕修复领域。 具有如下特点&#xff1a; 1…

详细描述一下CrossOver2024版本的用途和作用?

当然可以。CrossOver 是一款由 CODE WEAVERS 公司开发的软件&#xff0c;其主要目标是在 macOS 和 Linux 系统上实现与 Windows 应用程序的兼容性。它不同于传统的虚拟机&#xff0c;如 Parallels 或 VMware&#xff0c;因为它并不在 macOS 上创建一个完整的 Windows 环境。相反…

基于机器学习的青藏高原高寒沼泽湿地蒸散发插补研究_王秀英_2022

基于机器学习的青藏高原高寒沼泽湿地蒸散发插补研究_王秀英_2022 摘要关键词 1 材料和方法1.1 研究区概况与数据来源1.2 研究方法 2 结果和分析2.1 蒸散发通量观测数据缺省状况2.2 蒸散发与气象因子的相关性分析2.3 不同气象因子输入组合下各模型算法精度对比2.4 随机森林回归模…

安卓系统签名方法

首先在源码中创建key目录用来存放我们需要的文件&#xff0c;一般需要build/target/product/security/platform.pk8&#xff0c;build/target/product/security/platform.x509.pem&#xff0c;然后执行命令openssl pkcs8 -inform DER -nocrypt -in platform.pk8 -out platform.…

9.vue学习笔记(组件传递Props校验+组件事件-组件传递数据+组件事件-配合“v-model”使用)

文章目录 1.组件传递Props校验1.1.默认值1.2.必选项1.3.注意事项&#xff1a;props 是只读的 2.组件事件-组件传递数据2.1.温馨提示&#xff1a;组件之间传递数据的方案 3.组件事件-配合“v-model”使用 1.组件传递Props校验 Vue组件可以更细致地声明对传入的 props 的校验要求…

重铸安卓荣光——复选框ButtonCheckBox

痛点&#xff1a; 公司打算做安卓软件&#xff0c;最近在研究安卓&#xff0c;打算先绘制样式 研究发现安卓并不像前端有那么多组件库&#xff0c;甚至有些基础的组件都需要自己实现&#xff0c;记录一下自己实现的组件 成品展示 一个复选框样式 选中时背景橙色&#xff0c;带…