数据结构进阶篇 之 【堆的应用】(堆排序,TOP-K问题)详细讲解

news/2024/6/24 8:43:10/文章来源:https://blog.csdn.net/foodsx/article/details/137125853

在这里插入图片描述
所有人都关心我飞的高不高,只有我妈关心我翅膀硬不硬

一、堆的应用

1. 堆排序

1.1 建堆

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

2.TOP-K问题

二、完结撒❀

–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–
学习一个知识,我们起码要直到它的用途,那样才算学会了

一、堆的应用

1.堆排序

大家肯定都学过冒泡排序,快速排序等等,在学完堆之后我们也可以用堆来实现数据排序。
(ps:冒泡排序的时间复杂度:O(N^2))

1.1 建堆

升序:建大堆
降序:建小堆

建堆方式可能与大家预想的不太一样,但确实如此,升序我们需要建大堆,降序我们建小堆,再利用堆删除的思想进行排序,时间复杂度会低很多。

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

建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序
代码实现:

void Swap(HPDataType* px, HPDataType* py)
{HPDataType tmp = *px;*px = *py;*py = tmp;
}//向下调整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{//从左孩子开始,child为小孩子那个int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] > a[child + 1]){++child;}if (a[child] < a[parent])//小堆<,大堆>{Swap(&a[parent], &a[child]);parent = child;child = child * 2 + 1;}else{break;}}
}//升序  大堆 O(N*logN)
//降序  小堆 O(N*logN)
void HeapSort(HPDataType* a, int n)
{//根据数组直接建堆 O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdJustDown(a, n, i);}//交换根和尾的位置,再向下对前end(end每次少一个)的数进行调整 O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdJustDown(a, end, 0);--end;}
}

只需要将要排序的数组地址和数组元素的总个数作为实参传过来,并且会向下调整,就可以实现排序。
这样的堆排序时间复杂赋为O(N*logN)

我们拿一个数组以降序排小堆为大家举例讲解:

int arr[] = {5,2,3,6,1,4,7}

逻辑图解:

在这里插入图片描述
因为每次向下调整,根一定是数组中最小值,将最小值与当前数组访问的尾坐标进行交换,直到end为0,数组中的元素便以排好顺序。

2.TOP-K问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。

比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:

1. 用数据集合中前K个元素来建堆

             前k个最大的元素,则建小堆前k个最小的元素,则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

为了更好的给大家讲解,我们可以现根据文件操作手动造出一些数据来

代码如下:

//造数据
void CreateNDate()
{int n = 10000;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();fprintf(fin, "%d\n", x);}fclose(fin);
}

以读的方式在data.txt文件中造出10000个随机数
效果如下:
在这里插入图片描述当然,如果感觉10000个数据不够多,可以手动添加更多数据。

接下来我们就在这10000个数据中进行TOp-K问题的讲解

如何在这10000个数据中选出前K个最大的数呢?

上面对TOP-K问题的讲解已经给出了思路

我们可以先看一下代码实现:

//按照大小选出前k个值
void Tokp()
{//选出前k个最大数据printf("请输入前几个最大的值:>");int k = 0;scanf("%d", &k);//将数据中前k个数据存入到创建的minheap数组中const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");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]);}//建堆(向下建堆)for (int i = (k - 1 - 1) / 2; i >= 0; --i){AdJustDown(minheap, k, i);}//判断大小进行替换int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (minheap[0] < x){minheap[0] = x;AdJustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}fclose(fout);}

这里对文件操作函数比如:fscanf,fprintf等不太熟悉的同学建议去官网进行查询如何使用之后再进行Top-K问题的学习
官网网址:cplusplus

假设我们要前10个最大的数据,那么输入k为10.
实现逻辑步骤:

1.输入k为10
2.以读的方式打开data.txt文件
3.创建一个10个数据空间大小(单位为字节)的数组
4.将文件中前10个数存入到数组中
5.对数组进行向下建堆(这里我们要前10个最大的数据,所以要建小堆)
6.将根节点以此与剩余9990个数据进行对比,大于根节点就进行替换再对前十个数据进行向下调整
7.打印数组,关闭文件

因为创建的是小堆,那么根节点的值一定是堆中最小的,如果后续数据大于根节点的值,替换后再向下调整,最后对比完数据前十个建好的小堆数据就是这10000个数据中最大的10个。

调用函数打印结果:
在这里插入图片描述
因为10000个数据比较大,并且我们也并不知道这10000个数据中都有哪些数组,心里没有底
那么会不会有同学怀疑打印出的数值是否正确呢?

下面我教大家怎么检验所敲的该函数是否正确
我们可以在造数据的函数中做一些手脚
代码如下:

//造数据
void CreateNDate()
{int n = 100000;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)%10000;//检验程序准确fprintf(fin, "%d\n", x);}fclose(fin);
}

这次我们将造出来的随机数该成100000个(判断数据增多会不会出现BUG)
再将造出来的每一个随机数都加上i并且余上10000

因为随机数所返回的数值大小范围为30000左右,我们为了让造出来的数更加随机,就每次加上i
余上10000的目的是为了让造出来的数字都在0~9999之间

之后我们直接执行该函数

执行后打开data.txt文件夹,我们会看到100000个数值在0~9999之间的数组

我们在该文件夹中随机更改5个数字,将这5个数字都改成大于10000的值,越大越好,之后保存

再对该文件里的所有数值进行Tokp,假设输入k为10,那么最后出来结构只要包含我们所更改的5个数据,就说明该函数打印前k个最大数据是正确的。

二、完结撒❀

如果以上内容对你有帮助不妨点赞支持一下,以后还会分享更多编程知识,我们一起进步。
最后我想讲的是,据说点赞的都能找到漂亮女朋友❤
在这里插入图片描述

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

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

相关文章

每日面经分享(pytest测试案例,接口断言,多并发断言)

pytest对用户登录接口进行自动化脚本设计 a. 创建一个名为"test_login.py"的测试文件&#xff0c;编写以下测试脚本 import pytest import requests# 测试用例1&#xff1a;验证登录成功的情况 # 第一个测试用例验证登录成功的情况&#xff0c;发送有效的用户名和密…

网页的血液——javascript

JavaScript 基础知识概述 1. JavaScript 介绍 JavaScript 是一种高级的、解释型的编程语言&#xff0c;它是一种基于对象的、事件驱动的语言&#xff0c;它允许开发者创建动态的网页。JavaScript 是一种脚本语言&#xff0c;它可以嵌入到 HTML 中&#xff0c;或者作为外部文件…

聚焦新污染物,共谋治理策|中联环保圈

在环境污染防治的征途上&#xff0c;新污染物治理不仅是一场考验决心和毅力的攻坚战&#xff0c;更是对原有治理策略的广度和深度的全面拓展。这需要以更加坚定的决心&#xff0c;更加科学的策略&#xff0c;以及更加创新的思维来应对。 地方两会圆满闭幕之际&#xff0c;各地…

链表优化与拓展的细节:深度探索与精致打磨(续篇)

五、链表算法的优化与拓展 链表算法的优化与拓展是链表应用中不可或缺的一部分。通过对算法进行精细打磨和创新拓展&#xff0c;我们可以进一步提升链表处理数据的效率和灵活性。 排序算法的优化 链表常用于实现各种排序算法&#xff0c;如插入排序、归并排序等。然而&#…

视频推拉流EasyDSS点播平台云端录像播放异常的问题排查与解决

视频推拉流EasyDSS视频直播点播平台可提供一站式的视频转码、点播、直播、视频推拉流、播放H.265视频等服务&#xff0c;搭配RTMP高清摄像头使用&#xff0c;可将无人机设备的实时流推送到平台上&#xff0c;实现无人机视频推流直播、巡检等应用。 有用户反馈&#xff0c;项目现…

redis对象list

Redis List是一组连接起来的字符串集合。 写操作&#xff1a; LPUSH 语法:LPUSH key value [value …] 功能:从头部增加元素,返回值为List中元素的总数。 RPUSH 语法:RPUSH key value [value …] 功能:从尾部增加元素,返回值为List中元素的总数。 LPOP 语法:LPOP key 功能…

fastadmin学习07-无限级分类

create table fa_producttype (id int auto_increment comment 分类id,createtime bigint null comment 创建时间,updatetime bigint null comment 更新时间,deletetime bigint null comment 删除时间,name varchar(255) null comment 分类名称…

数论与线性代数——整除分块【数论分块】的【运用】【思考】【讲解】【证明(作者自己证的QWQ)】

文章目录 整除分块的思考与运用整除分块的时间复杂度证明 & 分块数量整除分块的公式 & 公式证明公式证明 代码code↓ 整除分块的思考与运用 整除分块是为了解决一个整数求和问题 题目的问题为&#xff1a; ∑ i 1 n ⌊ n i ⌋ \sum_{i1}^{n} \left \lfloor \frac{n}{…

用html实现在页面底部养鱼的效果

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>在网页底部养鱼</title><link rel"stylesheet" href"./style.css"> </head> <body> <div id"fi…

​ SpringBoot自动装配原理

SpringBoot自动装配原理 SpringBoot的启动类上有一个注解&#xff1a;SpringBootApplication 。该注解是三个注解的复合注解。 1.SpringBootConfiguration 注解 点进SpringBootConfiguration 注解&#xff0c;可以发现其核心注解为Configuration注解&#xff1a; Configuration…

Mysql 常用SQL语句

1、查看mysql中所有的数据库&#xff0c; show databases; 2、创建库 create database 库名;&#xff08;也可以用 create database if not exists 库名; 表示如果库不存在再创建&#xff09; 例&#xff1a;create database if not exists ecology; 3、删除库 …

Mysql数据库故障排查与优化

目录 前言 一、Mysql数据库的单实例故障 1.故障一——拒绝连接数据库 1.1故障内容 1.2问题分析 1.3解决方法 2.故障二——密码错误 2.1故障内容 2.2问题分析 2.3解决方法 3.故障三——数据库处理较慢 3.1故障内容 3.2问题分析 3.3解决方法 4.故障四——数据库表…

【leetcode】力扣简单题两数之和

题目 思路 代码实现 #include<iostream> #include<unordered_map>using namespace std;class Solution { public:vector<int> TwoNumber(const vector<int>& nums, int target){vector<int> number_vector;unordered_map<int, int> …

SpringCloud学习(1)-consul

consul下载安装及使用 1.consul简介 Consul是一种开源的、分布式的服务发现和配置管理工具&#xff0c;能够帮助开发人员构建和管理现代化的分布式系统。它提供了一套完整的功能&#xff0c;包括服务注册与发现、健康检查、KV存储、多数据中心支持等&#xff0c;可以帮助开发人…

代码随想录算法训练营第39天|62.不同路径 |63. 不同路径 II

代码随想录算法训练营第39天|62.不同路径 |63. 不同路径 II 详细布置 62.不同路径 本题大家掌握动态规划的方法就可以。 数论方法 有点非主流&#xff0c;很难想到。 https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html 视频讲解&#xff1a;https…

深入了解C语言中的结构体类型与内存对齐

引言&#xff1a; 在C语言中&#xff0c;结构体是一种自定义的数据类型&#xff0c;它允许我们将不同类型的数据组合在一起&#xff0c;形成一个新的数据类型。结构体的使用为我们解决了一些复杂数据的表示和处理问题&#xff0c;不仅限于单单的整型或者字符。本文将深入探讨结…

网络编程--高并发服务器(二)

这里写目录标题 线程池高并发服务器UDP服务器TCP与UDP机制的对比TCP与UDP优缺点比较UDP的C/S模型实现思路模型分析实现思路&#xff08;对照TCP的C/S模型&#xff09; recvfrom函数、sendto函数 一级目录二级目录二级目录二级目录 一级目录二级目录二级目录二级目录 一级目录二…

C++引用与指针比较

引子&#xff1a; 问题&#xff1a; 指针指向变量必须类型一致&#xff08;int对int*类型指针&#xff09;&#xff0c;这样计算&#xff0c;解引用才能得到正确的结果&#xff0c;那引用也是如此吗&#xff1f; 回答&#xff1a;&#xff08;常引用&#xff09; 从语法来说…

MyBatis主要的类层次结构(Mybatis工具类)

MyBatis主要的类层次结构 每一个MyBatis的应用程序都以一个SqlSessionFactory 对象的实例为核心 。 SqlSessionFactory对象的实例可以通过SqlSessionFactoryBuilder对象来获得 。 SqlSessionFactoryBuilder对象可以从 XML 配置文件中构建 SqlSessionFactory对象。 package…

RN实现全局数据共享(非Redux,使用原生内置的方法实现)

下面这个方法是在RN使用全局数据共享的,使用原生React的方式搞得,相对于Redux配置相对简单,适合小型项目 项目内创建MyContext.js // MyContext.jsimport React from react;const MyContext React.createContext();export default MyContext;App.js引入 // App.jsimport Rea…