【数据结构与算法】之堆的应用——堆排序及Top_K问题!

目录

1、堆排序

2、Top_K问题

3、完结散花


                                                                                个人主页:秋风起,再归来~

                                                                                            数据结构与算法                             

                                                                       个人格言:悟已往之不谏,知来者犹可追

                                                                                        克心守己,律己则安!

1、堆排序

对一个无序的数组,因为数组中的元素是连续的,那我们就可以将数组中的元素进行建堆排序!

假设我们要对一个数组中的元素进行降序,那我们就要先将其进行向下调整建小堆,再将堆顶元素与堆的最后一个元素交换,那么数组中最小的那个元素就到最后面去了,最后一个数有序后,那我们就不再把它看作堆的元素了,最后再在堆顶进行向下调整保证小堆不变。这是一趟,假设数组中有N个元素,那我们进行(N-1)趟就行了。

下面是图解:

 代码:

//交换
void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向上调整
void AdjustUp(int* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent])//< 建小堆;> 建大堆{swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//向下调整
void AdjustDown(int* a, int size, int parent)
{//先假设做孩子小int child = parent * 2 + 1;while (child < 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 HeapSort(int* a, int len)
{//建堆算法一(从第一个孩子向上调整)//这种写法的时间复杂度为n*logn//for (int i = 1; i < len; i++)//{//	AdjustUp(a, i);//从第一个孩子向上调整建堆//}// //建堆算法二(从倒数第一个根向下调整)//这种写法的时间复杂度为O(N)[更优]for (int i = (len-1-1)/2; i >= 0; i--){AdjustDown(a, len,i);//从倒数第一个根向下调整建堆}int end = len - 1;while (end > 0){swap(&a[0], &a[end]);//交换第一个数与最后一个数end--;AdjustDown(a, end, 0);}
}int main()
{int a[] = { 1,2,4,5,6,8,9,10 };int len = sizeof(a) / sizeof(a[0]);HeapSort(a, len);for (int i = 0; i < len; i++){printf("%d ", a[i]);}return 0;
}

 

2、Top_K问题

 Top_K问题:

Top_K问题就是在大量数据中找出最大或最小的前K个

我们可以很轻松的想到用将这些全部数据进行建堆,在进行K次pop,这样我们就很容易的就可以找到最大或最小的前K个。但这里有一个问题,就是存储这么的数据势必会用到大量的空间,那我们有没有其他方法,在用到极小的的空间内解决问题呢?

当然可以!

假设我们要找出最大的前K个~

1、我们先将全部数据的前K个建成小堆

2、再将后N-K个数据分别和堆顶数据比较,比堆顶数据大就将堆顶数据覆盖

3、然后再从堆顶向下调整保持小堆结构

4、将后N-K个数据比较完后,小堆里面的数据就是最大的前K个

我这里先随机生成10万个随机数并且这些随机数都小于10万,并将这些数据都写进我们的文本文件中!

void CreatRandomNumber()
{FILE* pf = fopen("test.txt", "w");if (pf == NULL){perror("fopen fail!\n");return;}srand((unsigned int)time(NULL));int n = 100000;//随机生成10万个数for (int i = 0; i < n; i++){int x = (rand() + i) % 100000;//这些数的大小都小于10万(方便后面检测)fprintf(pf, "%d\n", x);//将数据写入文件当中}fclose(pf);
}
void TestTopK()
{FILE* pf = fopen("test.txt", "r");if (pf == NULL){perror("fopen fail!\n");return;}int k = 0;printf("请输入您要的前K个数:");scanf("%d", & k);int* HeapTopK = (int*)malloc(sizeof(int) * k);//在文件中读取K个数放到数组中for (int i = 0; i < k; i++){fscanf(pf, "%d", &HeapTopK[i]);}//将这K个数建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(HeapTopK, k, i);//向下调整建堆}int x = 0;//在10万个数中找前K个数while (fscanf(pf, "%d", &x)>0){if (x > HeapTopK[0]){HeapTopK[0] = x;AdjustDown(HeapTopK, k, 0); }}HeapSort(HeapTopK, k);//打印前k个数for (int i = 0; i < k; i++){printf("%d ", HeapTopK[i]);}free(HeapTopK);HeapTopK = NULL;fclose(pf);
}
int main()
{//CreatRandomNumber();TestTopK();return 0;
}

为了检查结果是否准确,我在文件中随机将10个数的大小手动调整成大于十万!

让我们来看看结果!

3、完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

​​​​

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

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

相关文章

焦化超低排平台选哪家好?(已解答)

在环保政策日益严格的背景下&#xff0c;焦化行业的超低排放改造成为企业转型升级的必经之路。朗观视觉小编建议&#xff0c;选择合适的焦化超低排平台对于确保改造效果和实现可持续发展具有重要意义。本文将从多个维度为您提供一份全面的评估与选择指南&#xff0c;帮助您在众…

【计算机毕业设计】030英语学习交流平台微信小程序

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

Volatile的内存语义

1、volatile的特性 可见性&#xff1a;对一个volatile变量的读&#xff0c;总能够看到任意一个线程对这个volatile变量的写入。 原子性&#xff1a;对任意单个volatile变量的读/写具有原子性&#xff0c;但类似于volatile这种复合操作不具有原子性。 接下来我们用程序验证。…

Spring Cloud 系列之Gateway:(9)初识网关

传送门 Spring Cloud Alibaba系列之nacos&#xff1a;(1)安装 Spring Cloud Alibaba系列之nacos&#xff1a;(2)单机模式支持mysql Spring Cloud Alibaba系列之nacos&#xff1a;(3)服务注册发现 Spring Cloud 系列之OpenFeign&#xff1a;(4)集成OpenFeign Spring Cloud …

【2024软考】史上最全!软考刷题+解析大合集(9万字全手工打,货真价实)

计算机基础知识 1.中断向量表用来保存各个中断源的中断服务程序的入口地址。当外设发出中断请求信号&#xff08;INTR&#xff09;以后&#xff0c;由中断控制器&#xff08;INTC&#xff09;确定其中断号&#xff0c;并根据中断号查找中断向量表来取得其中断服务程序的入口地…

89.网络游戏逆向分析与漏洞攻防-游戏技能系统分析-游戏中使用的哈希算法逆向分析

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 如果看不懂、不知道现在做的什么&#xff0c;那就跟着做完看效果&#xff0c;代码看不懂是正常的&#xff0c;只要会抄就行&#xff0c;抄着抄着就能懂了 内容…

HMI设计:再谈上位机与下位机,附海量案例图

上期回顾&#xff1a;HMI界面之&#xff1a;上位机界面设计&#xff0c;一文扫盲 一、上位机负责控制和决策&#xff0c;下位机负责采集和执行 上位机和下位机是两个概念&#xff0c;通常用于描述计算机系统中不同层次的设备或组件。 上位机&#xff08;Host Computer&#x…

kubernetes之prometheus kube-controller-manager。 scheduler报错问题

项目场景&#xff1a; prometheus scheduler及kube-controller-manager监控报错 问题描述 kubeadm搭建完kube-prometheus 会有这个报错 原因分析&#xff1a; rootmaster2:~# kubectl describe servicemonitor -n kube-system kube-controller-manager通过以上图片我们发现 k…

解决GoLand无法Debug

goland 调试的的时候提示如下错误 WARNING: undefined behavior - version of Delve is too old for Go version 1.22.3 (maximum supported v 其实个原因是因为正在使用的Delve调试器版本太旧&#xff0c;无法兼容当前的Go语言版本1.22.3。Delve是Go语言的一个调试工具&#…

【vue-5】双向数据绑定v-model及修饰符

单向数据绑定&#xff1a;当数据发生改变时&#xff0c;视图会自动更新&#xff0c;但当用户手动更改input的值&#xff0c;数据不会自动更新&#xff1b; 双向数据绑定&#xff1a;当数据发生改变时&#xff0c;视图会自动更新&#xff0c;但当用户手动更改input的值&#xf…

好用的window粘贴板

可以设置指定的快捷键&#xff0c;在需要使用最近复制的记录时快速的复用 -> Ditto。 选择Download即可 地址&#xff1a;Ditto clipboard manager (sourceforge.io)https://ditto-cp.sourceforge.io/

IOS开发者证书快捷申请

App Uploader 在进行iOS应用开发中,可以借助appuploader辅助工具进行证书制作、上传和安装测试等操作。首先,您需要访问官方网站获取最新版本的appuploader。最新版本已经优化了与Apple账号的登录流程,无需支付688元,并提供了Windows版和Mac版供用户选择。下载完成后,解压…

C#_库的引用

类库的引用 还可以自己引用类库&#xff1a;解决方案-添加-新建项目 主程序 using System; using System.Windows.Forms; using Tools;namespace ConsoleApp2 {class Program{static void Main(string[] args){//Console.WriteLine("helloword");// Form form ne…

非整数倍数据位宽转换24to128

描述 实现数据位宽转换电路&#xff0c;实现24bit数据输入转换为128bit数据输出。其中&#xff0c;先到的数据应置于输出的高bit位。 电路的接口如下图所示。valid_in用来指示数据输入data_in的有效性&#xff0c;valid_out用来指示数据输出data_out的有效性&#xff1b;clk是时…

VUE2 tab切换导航 展示页面内容(父级子级独立)

VUE2 tab切换导航 展示页面内容 父级子级独立 图片示例代码 图片示例 代码 <template><div class"center"><!-- 一级导航 --><div class"menu"><div class"menu_list"><div v-for"item of List" :k…

常见算法(3)

1.Arrays 它是一个工具类&#xff0c;主要掌握的其中一个方法是srot&#xff08;数组&#xff0c;排序规则&#xff09;。 o1-o2是升序排列&#xff0c;o2-o1是降序排列。 package test02; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparat…

C#【进阶】迭代器

迭代器 文章目录 1、迭代器概念2、标准迭代器的实现方法3、用yield return 语法糖实现迭代器4、用yield return 语法糖为泛型类实现迭代器 1、迭代器概念 迭代器&#xff08;iterator&#xff09; 又称光标&#xff08;cursor&#xff09; 是程序设计的软件设计模式 迭代器提供…

IPv6 地址创建 EUI-64 格式接口 ID 的过程

IPv6 接口标识符 IPv6 地址中的接口标识符&#xff08;ID&#xff09;用于识别链路上的唯一接口&#xff0c;有时被称为 IPv6 地址的 “主机部分”。接口 ID 在链路上必须是唯一的&#xff0c;始终为 64 位长&#xff0c;并且可以根据数据链路层地址动态创建。 MAC 地址 中的…

操作系统入门系列-MIT6.828(操作系统工程)学习笔记(一)---- 操作系统介绍与接口示例

MIT6.S081&#xff08;操作系统&#xff09;学习笔记 操作系统入门系列-MIT6.S081&#xff08;操作系统&#xff09;学习笔记&#xff08;一&#xff09;---- 操作系统介绍与接口示例 操作系统入门系列-MIT6.828&#xff08;操作系统工程&#xff09;学习笔记&#xff08;二&a…

Jenkins在windows上进行安装

今天为了实现jmeter接口测试脚本的持续性集成安装了jenkins&#xff0c;主要记录jenkins的安装和端口的修改。 前提条件&#xff1a;安装了jdk&#xff0c;我本机安装的jdk1.8。 1.下载jenkins安装包 安装jenkins我们需要先下载安装包&#xff0c;可以通过下面的链接进行下载&a…