数据结构之堆排序以及Top-k问题详细解析

个人主页：点我进入主页

专栏分类：C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶

C语言刷题       数据结构初阶

欢迎大家点赞，评论，收藏。

一起努力

目录

1.前言

2.堆排序

2.1降序排序

2.2时间复杂度

3.Top-k问题

4.总结

1.前言

        在上一篇文章中我们主要讲解了关于大堆和小堆的代码实现，今天我们主要讲解关于堆排序以及堆排序的时间复杂度，我们会讲解关于经典的Top-k问题进行讲解（其中我会伪造一些数据来展示），今天的内容比上次的内容更加的爽，更有挑战性，其中的奥妙真的无法用语言来形容，接下来就让我们感受一下吧。

2.堆排序

        我们对数组进行降序排序，我们使用堆排序，在这里由于升序和降序的思想基本一致，只需要修改一些符号即可完成转化，所以我们只讲关于降序的内容。

2.1降序排序

        在上次的内容中我们使用向上调整来创建堆，我们是创建小堆还是大堆呢？我们想让数据进行降序，如果我们使用大堆的话堆的第一个数是最大的，我们取出来之后堆的顺序就乱了，我们需要重新进行大堆排序，那么我们的时间复杂度为O(n^2*logn),这比我们的冒泡排序还要慢，所以大堆是不可以的，所以我们选择小堆排序，我们这次依旧使用想上调整，详细代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
void Swap(int* num1, int* num2)
{int temp = *num1;*num1 = *num2;*num2 = temp;
}
void print(int* arr, int size)
{for (int i = 0; i < size; i++)printf("%d ", arr[i]);
}
void AdJustUp(int* arr, int sz,int size)
{assert(arr);int child = sz, parent = (child - 1) / 2;while (child>0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}
void AdJustDown(int* arr, int i, int size)
{assert(arr);int parent = i, child = 2 * parent + 1;while (child<size){if (child + 1 < size && arr[child] >arr[child + 1]){child++;}if (arr[parent] > arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = 2 * parent + 1;}elsebreak;}
}
void HeapSort(int* arr, int n)
{assert(arr);for (int i = 0; i < n; i++){AdJustUp(arr, i, n);}for (int i = 0; i < n-1; i++){Swap(&arr[0], &arr[n - 1 - i]);AdJustDown(arr, 0, n - 1 - i);}}
int main()
{int arr[10];int n = 10;for (int i = 0; i < n; i++){arr[i] = i;}HeapSort(arr,n);print(arr, n);return 0;
}

我们的运行结构如下：

事实上我们这不是我们的堆排序，真正的堆排序在第一次创建小堆时代码为：

	for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdJustDown(arr, 0, n - 1 - i);}

向下调整为什么可以实现呢？，我们知道向下调整是左边和右边都是小堆然后根节点是新插入的我们就可以利用向下调整进行排序，那我们在最后一个节点的父节点进行向下调整，让他们都成为小堆，这样我们就可以完成小堆的创建。那为什么采用这种形式呢？仅仅是因为代码少吗？事实上这与我们的时间复杂度有关。

2.2时间复杂度

        我们看利用向上调整建立小堆的时间复杂度，我们第k层有2^(k-1)个节点，每个节点需要向上调整k-1次共调整(k-1)*2^(k-1)次，第k-1层有2^(k-2)，每个节点需要调整k-2次，共调整(k-2)*2^(k-2)……第二层有2^1个节点，每个节点需要调整1次，第一层有2^0个节需要调整0次，共需要调整T(k)=0*2^0+1*2^1+……+(k-2)*2^(k-2)+(k-1)*2^(k-1),我们化简可以得到T(k)=(k-2)2^k+2;其中k=logN,所以T(k)=NlogN;但是我们采用向下调整我们第k层有我们第k层有2^(k-1)个节点，每个节点需要向上调整0次共调整0*2^(k-1)次，第k-1层有2^(k-2)，每个节点需要调整1次，共调整1*2^(k-2)……第二层有2^1个节点，每个节点需要调整k-2次，第一层有2^0个节需要调整k-1次,共需要调整T(k)=(k-1)*2^0+(k-2)*2^1+……+1*2^(k-2)+0*2^(k-1),我们化简得到T(k)=2^k-k-1，其中k=logN,故T(k)=N-logN;可以看到向下调整建立堆时间复杂度低，所以我们选择向下调整这大大减少了我们的运算时间。

3.Top-k问题

        有一个问题是我们在一组数中(共N个数)找到最小的k个数，其中N远大于k，让我们找到前k个数，当数据很小的时候我们利用堆排序进行查找很容易，但是当数据量特别大的时候我们就很难实现，因为数据占用的内存太大了，例如我们要在1百亿个数据中找到前10个最小的数，100万个整形数据相当于占用37GB,这样我们就很难处理，这时候就出现了我们的Top-k问题，我们是如何解决这个问题呢？这时候我们由于需要找最小的前10个数据我们创建一个大堆，然后输入一个数据就将堆顶元素替换然后再向下调整这样就可以找到最小的10个数据，我们创建100万个数据进行模拟，我们的代码如下：

我们将数据放在文件中，生成data.txt文件

#include<stdio.h>
int main()
{FILE* pf = fopen("data.txt", "w");if (pf == NULL){perror("fopen fail");return 1;}for (int i = 0; i < 1000000; i++){fprintf(pf,"%d\n", i);}fclose(pf);pf = NULL;return 0;
}

修改其中的10个数据让他成为我们的结果，然后进行下一步找到这k个数

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int MyHeapData;
typedef struct Heap {MyHeapData* data;int size;int capacity;
}Heap;
void HeapInit(Heap* php)
{assert(php);php->data = (MyHeapData*)malloc(sizeof(MyHeapData)*10);php->size = 0;
}
void Swap(int* num1, int* num2)
{int temp = *num1;*num1 = *num2;*num2 = temp;
}
void AdJustDown(int* arr, int n, int i)
{assert(arr);int parent = 0, child = 2 * parent + 1;while (child<n){if (child+1<n&&arr[child] < arr[child + 1]){child++;}if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
void AdJustUp(MyHeapData* arr, int size)
{assert(arr);int child = size - 1, parent = (child - 1) / 2;while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}
int main()
{//FILE* pf = fopen("data.txt", "w");//if (pf == NULL)//{//	perror("fopen fail");//	return 1;//}//for (int i = 0; i < 1000000; i++)//{//	fprintf(pf,"%d\n", i);//}//fclose(pf);//pf = NULL;FILE* pf = fopen("data.txt", "r");if (pf == NULL){perror("fopen fail");return 1;}int data;int i;Heap ph ;HeapInit(&ph);for (i = 0; i < 10; i++){fscanf(pf, "%d", &data);ph.data[i] = data;AdJustUp(ph.data, i);}while (fscanf(pf, "%d", &data) != EOF){if(data<ph.data[0])Swap(&data, &ph.data[0]);AdJustDown(ph.data, 10, 0);}for (i = 0; i < 10; i++){printf("%d ", ph.data[i]);}fclose(pf);pf = NULL;return 0;
}

运行结果如下：

这就是我们经典的Top-k问题；

4.总结

        今天的内容到这里就结束了，希望大家可以好好的理解今天的内容，欢迎大家来三连。

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

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

相关文章

C++ 抽象类和接口 详解

C++ 抽象类和接口 详解

目录 0 引言1 抽象类2 接口2.1 Java与C接口的区别 &#x1f64b;‍♂️ 作者&#xff1a;海码007&#x1f4dc; 专栏&#xff1a;C专栏&#x1f4a5; 标题&#xff1a;C 抽象类和接口 详解❣️ 寄语&#xff1a;书到用时方恨少&#xff0c;事非经过不知难&#xff01;&#x1f…
阅读更多...
Python的模块与库，及if __name__ == ‘__main__语句【侯小啾python领航班系列（二十四）】

Python的模块与库，及if __name__ == ‘__main__语句【侯小啾python领航班系列（二十四）】

Python的模块与库，及if name == __main__语句【侯小啾python领航班系列（二十四）】 大家好，我是博主侯小啾， 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ…
阅读更多...
【拓展】Loguru：更为优雅、简洁的Python 日志管理模块

【拓展】Loguru：更为优雅、简洁的Python 日志管理模块

目录 一、简单介绍 二、安装与简单使用 ​三、常见用法 3.1 显示格式 3.2 写入文件 3.3 json日志 3.4 日志绕接 3.5 并发安全 四、高级用法 4.1 接管标准日志logging 4.2 输出日志到网络服务器 4.2.1 自定义日志服务器 ​4.2.2 第三方库日志服务器 4.3 与pytest结…
阅读更多...
LED屏幕信息安全如何预防？

LED屏幕信息安全如何预防？

随着科技的不断进步&#xff0c;LED屏幕在我们生活和工作中扮演着越来越重要的角色&#xff0c;然而&#xff0c;随之而来的是信息安全面临的挑战。为了有效预防LED屏幕信息的泄露和被盗取&#xff0c;我们需要采取一系列的安全措施。以下是一些建议&#xff1a; 物理安全措施&…
阅读更多...
长度最小的子数组（Java详解）

长度最小的子数组（Java详解）

目录 题目描述 题解 思路分析 暴力枚举代码 滑动窗口代码 题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条…
阅读更多...
单片机学习11——矩阵键盘

单片机学习11——矩阵键盘

矩阵键盘&#xff1a; 这个矩阵键盘可以接到P0、P1、P2、P3都是可以的。 使用矩阵键盘是能节省单片机的IO口。 P3.0 P3.1 P3.2 P3.3 称之为行号。 P3.4 P3.5 P3.6 P3.7 称之为列号。 矩阵键盘检测原理&#xff1a; 1、检查是否有键按下&#xff1b; 2、键的抖动处理&#xf…
阅读更多...
Redis的安装

Redis的安装

本文采用原生的方式安装Redis&#xff0c;Redis的版本为5.0.5 安装 下载 下载网站&#xff1a;https://download.redis.io/releases/ wget http://download.redis.io/releases/redis-5.0.5.tar.gz解压 tar -zxvf redis-5.0.5.tar.gz进入redis目录 cd redis-5.0.5执行编译…
阅读更多...
面试--各种场景问题总结

面试--各种场景问题总结

1.在开发过程中&#xff0c;你是如何保证机票系统的正常运行的&#xff1f; 用户、测试、监控和日志、安全措施、数据备份、系统设计、需求分析 2.在机票系统开发过程中&#xff0c;你最有成就的事情&#xff0c;为什么&#xff1f; 用户体验感、高可用和稳定性、客户满意度、系…
阅读更多...
IdleStateHandler 心跳机制源码详解

IdleStateHandler 心跳机制源码详解

优质博文&#xff1a;IT-BLOG-CN 一、心跳机制 Netty支持心跳机制&#xff0c;可以检测远程服务端是否存活或者活跃。心跳是在TCP长连接中&#xff0c;客户端和服务端定时向对方发送数据包通知对方自己还在线&#xff0c;保证连接的有效性的一种机制。在服务器和客户端之间一…
阅读更多...
vscode非常好用的扩展插件

vscode非常好用的扩展插件

1、Code Spell Checker&#xff1a; 帮助我们检查单词是否拼写错误&#xff0c;检查规则遵循驼峰拼写法。 2、Color Highlight&#xff1a;高亮显示颜色值 3、Svg Preview&#xff1a; 实时预览svg图片&#xff08;修改width、height、fill等值来实时查看效果&#xff09; 4、…
阅读更多...
人工智能(pytorch)搭建模型21-基于pytorch搭建卷积神经网络VoVNetV2模型，并利用简单数据进行快速训练

人工智能(pytorch)搭建模型21-基于pytorch搭建卷积神经网络VoVNetV2模型，并利用简单数据进行快速训练

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能(pytorch)搭建模型21-基于pytorch搭建卷积神经网络VoVNetV2模型&#xff0c;并利用简单数据进行快速训练。VoVNetV2模型是计算机视觉领域的一个重要研究成果&#xff0c;它采用了Voice of Visual Residual&…
阅读更多...
第十五届蓝桥杯模拟赛（第二期）

第十五届蓝桥杯模拟赛（第二期）

大家好&#xff0c;我是晴天学长&#xff0c;本次分享&#xff0c;制作不易&#xff0c;本次题解只用于学习用途&#xff0c;如果有考试需要的小伙伴请考完试再来看题解进行学习&#xff0c;需要的小伙伴可以点赞关注评论一波哦&#xff01;后续会继续更新第三期的。&#x1f4…
阅读更多...
wvp gb28181 pro 平台国标级连功能说明

wvp gb28181 pro 平台国标级连功能说明

国标28181不同平台之间支持两种连接方式&#xff0c;平级和上下级&#xff0c;WVP目前支持向上级级联。 测试环境 测试平台上级&#xff1a;192.168.10.209&#xff08;Alam centos8&#xff09; 测试平台下级&#xff1a;192.168.10.206&#xff08;ky10_x86&#xff09; 下级…
阅读更多...
VUE语法-ref和reactive响应式数据引用

VUE语法-ref和reactive响应式数据引用

1、响应式概述 在vue中定义一个参数&#xff0c;当这个参数在使用中发生了变化&#xff0c;在页面中对这个数据应用的地方都会同步的发生变化&#xff0c;这个就是数据响应式。 2、创建一个非响应式的参数 该程序中采用的是VUE3的用法&#xff1a; 1、在程序中定义了一个局…
阅读更多...
应用于智慧金融的AI边缘计算盒子+AI算法软硬一体化方案

应用于智慧金融的AI边缘计算盒子+AI算法软硬一体化方案

传统金融营业厅存在运营管理模式落后、资源投放不平衡、从业人员培训效果不达预期、客户体验割裂等普遍现象&#xff1b; 部署英码数字金融解决方案&#xff0c;将助力企业从传统金融模式快速向数字金融模式转变&#xff0c;可针对每一个客户定制个性化“一对一”服务&#xff…
阅读更多...
【栈和队列（2）】

【栈和队列（2）】

文章目录 前言队列队列方法队列模拟实现循环队列练习1 队列实现栈 前言 队列和栈是相反的&#xff0c;栈是先进后出&#xff0c;队列是先进先出&#xff0c;相当于排队打饭&#xff0c;排第一的是最先打到饭出去的。 队列 队列&#xff1a;只允许在一端进行插入数据操作&…
阅读更多...
MySQL 8创建数据库、数据表、插入数据并且查询数据

MySQL 8创建数据库、数据表、插入数据并且查询数据

我使用的数据库是MySQL 8。 创建数据库 create database Bookbought; -- 创建数据库Bookbought use Bookbought; -- 使用数据库Bookbought创建数据表 创建用户表bookuser。 create table ## 往allbook里边插入数据(id INT PRIMARY KEY AUTO_INCREMENT, -- id 为 主键userna…
阅读更多...
Golang数据类型（字符串）

Golang数据类型（字符串）

字符串重要概念 根据Go语言官方的定义&#xff1a; In Go, a string is in effect a read-only slice of bytes. 意思是Go中的字符串是一组只读的字节切片&#xff08;slice of bytes&#xff09;&#xff0c;每个字符串都使用一个或多个字节表示&#xff08;当字符为 ASCII 码…
阅读更多...
OpenWrt作为旁路由（网关）配置

OpenWrt作为旁路由（网关）配置

目录 背景前提条件环境操作步骤物理层连接设置与主路由同一网段禁用IPv6取消LAN接口桥接防火墙配置 背景 本文简介如何配置OpenWrt&#xff0c;使其作为旁路由&#xff08;网关&#xff09;运行。 旁路由大概有以下这几种工作方式&#xff1a; 主路由开DHCP&#xff0c;网关未…
阅读更多...
LeetCode刷题---反转链表

LeetCode刷题---反转链表

个人主页&#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏&#xff1a;http://t.csdnimg.cn/ZxuNL http://t.csdnimg.cn/c9twt 前言&#xff1a;这个专栏主要讲述递归递归、搜索与回溯算法&#xff0c;所以下面题目主要也是这些算法做的 我讲述…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023