当前位置: 首页 > news >正文

【数据结构】建堆算法复杂度分析及TOP-K问题

【数据结构】建堆算法复杂度分析及TOP-K问题

🔥个人主页大白的编程日记

🔥专栏数据结构


文章目录

  • 【数据结构】建堆算法复杂度分析及TOP-K问题
    • 前言
    • 一.复杂度分析
      • 1.1向下建堆复杂度
      • 1.2向上建堆复杂度
      • 1.3堆排序复杂度
    • 二.TOP-K问题
      • 2.1思路分析
      • 2.2代码实现
    • 后言

前言

哈喽,各位小伙伴大家好!上期我们讲了堆排序和建堆算法。今天我们就来分析一下他们的时间复杂度。话不多说,咱们进入正题。向大厂冲锋!

一.复杂度分析

我们都知道堆是一个完全二叉树。那他的高度h和节点数量N有什么关系呢?

那我们再来对比一下满二叉树和完全二叉树的高度h.

我们用大O渐进表示法看的话他们两个的高度h都可以认为是logN的量级
所以我们的堆的上下调整可以认为是logN,也就是高度次。

因为堆是完全二叉树,而满二叉树也是完全二叉树,所以为了方便证明
我们使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个结点不影响最终结果):

1.1向下建堆复杂度

我们先分别算出第一层到h-1层的节点个数和该层节点的调整次数
然后再推出总的调整次数。

  • 推导

1.2向上建堆复杂度

我们先分别算出第2层到h层的节点个数和该层节点的调整次数
然后再推出总的调整次数。

  • 推导

所以向下建堆的时间复杂度是O(N),向上建堆的复杂度是O(N*logN).
所以以后我们都尽量使用向下调整建堆。因为他的效率更高。

1.3堆排序复杂度

现在我们来看一下我们堆排序的时间复杂度是多少呢?

  • 推导

    堆排序的复杂度是O(N*logN).

二.TOP-K问题

2.1思路分析

我们的堆除了可以用来排序还可以用来解决经典的TOP-K问题。
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

  • 方法一
    我们很容易想到直接排序然后取出前K个即可。
    但是这个方法有个致命缺陷。
    如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。

    我们发现这个方法在数据量太大的时候并不适用。
    那有什么其他好的方法吗?
  • 方法二
    最佳的方式就是用堆来解决,基本思路如下:
    1 .用数据集合中前K个元素来建堆
    前k个最大的元素,则建K个数的小堆
    前k个最小的元素,则建K个数的大堆
    2 . 用剩余的N-K个元素依次与堆顶元素来比较,
    如果比堆顶元素还要大或小(小堆大 大堆小)则替换堆顶元素,然后向下调整重新建堆。

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

为什么呢?

  • 证明

    我们通过N-K次比较就可以筛选出N-K个不满足最大前K个数的数
    剩下在堆的数就是最大的前K个。
  • 疑问

我们用反证法可以得知这种情况不存在。

2.2代码实现

  • 生成数据函数
    我们先用srand生成不同的种子防止生成的随机数是伪随机数。
    然后fopen打开文件。循环生成随机数然后写入文件即可。最后关闭文件。
void CreatData()
{int n = 100000;//生成10万个数据srand(time(0));//生成不同的种子FILE* pf = fopen("test.txt", "w");//打开文件for (int i = 0; i < n; i++){int x = rand() % 100001+i;//生成随机数fprintf(pf, "%d\n", x);//写数据}fclose(pf);//关闭文件pf = NULL;
}


这样10万个数据就生成好了。

  • 比较函数

我们先接收k。然后开好k个数是堆空间。
然后从文件读取前k个数并填充到堆里面。然后建堆
然后继续读取文件里的数据直到文件末尾(返回EOF)
然后当数据大于堆顶元素是在进堆,然后重新调整建堆即可。

void test()
{int k;printf("请输入前K个数:");scanf("%d", &k);int* a = (int*)malloc(sizeof(int) * k);//开空间建堆FILE* pf = fopen("test.txt", "r");for (int i = 0; i < k; i++){fscanf(pf, "%d", &a[i]);}//填充数据for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, k, i);}//建小堆int x;while (fscanf(pf, "%d", &x) !=EOF){if (x > a[0]){a[0] = x;AdjustDown(a, k, 0);}}//对比for (int i = 0; i < k; i++){printf("%d ", a[i]);}//打印
}
  • 检验

那我们如何确保这10个数一定是最大的呢?万一我们的算法写错不是最大的前10个数怎么办?










那我们就可以在不同的地方在一些k标点。
也就是K个很大的数,确保他们是最大的前K个。
然后只需要看结果是不是这k个数即可。

大家发现结果就是我们手动给的这10个数。说明我们的程序时没问题的。

后言

这就是建堆算法复杂度分析及TOP-K问题。这里涉及到许多数学知识。大家可以多看几遍证明图。今天就分享到这里。感谢大佬们垂阅!咱们下期见!拜拜~

相关文章:

【数据结构】建堆算法复杂度分析及TOP-K问题

【数据结构】建堆算法复杂度分析及TOP-K问题 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;数据结构 文章目录 【数据结构】建堆算法复杂度分析及TOP-K问题前言一.复杂度分析1.1向下建堆复杂度1.2向上建堆复杂度1.3堆排序复杂度 二.TOP-K问…...

Thinkphp5实现前后端通过接口通讯基本操作方法

在ThinkPHP5框架中&#xff0c;实现前后端通过接口通讯是一个常见的需求&#xff0c;尤其是在开发RESTful API时。下面是一个基本的步骤指南&#xff0c;用于设置ThinkPHP5来创建API接口&#xff0c;并使前端能够通过HTTP请求与后端进行通讯。 1. 创建API模块 首先&#xff0…...

Go 语言任务编排 WaitGroup

WaitGroup 是常用的 Go 同步原语之一,用来做任务编排。它要解决的就是并发-等待的问题: 现在有一个 goroutine A 在检查点 ( checkpoint ) 等待一组 goroutine 全部完成它们的任务,如果这些 goroutine 还没全部完成任务,那么 goroutine A 就会被阻塞在检查点,直到所有的 …...

星环科技推出知识库产品 AI PC时代数据交互方式变革

随着企业业务的快速发展&#xff0c;数据量呈爆炸式增长&#xff0c;有效的知识管理成为企业面临的重要问题。企业遇到的普遍问题是大量的结构化、半结构化数据存储在不同的系统中&#xff0c;需要用多种计算机语言进行检索。而大模型彻底改变了人们和数据的交互方式&#xff0…...

10道JVM经典面试题

1、 JVM中&#xff0c;new出来的对象是在哪个区&#xff1f; 2、 说说类加载有哪些步骤&#xff1f; 3、 JMM是什么&#xff1f; 4、 说说JVM内存结构&#xff1f; 5、 MinorGC和FullGC有什么区别&#xff1f; 6、 什么是STW? 7、 什么情况下会发生堆/栈溢出&#xff1f…...

Redisson常用的数据结构及应用场景

Redisson 提供了一系列高级数据结构&#xff0c;这些数据结构封装了 Redis 的原生数据类型&#xff0c;提供了 Java API 的便利性和分布式特性。以下是 Redisson 中一些常用的数据结构&#xff0c;场景还在不断完善中&#xff1a; RBucket&#xff1a;这是一个简单的键值对存储…...

【实现100个unity特效之8】使用ShaderGraph实现2d贴图中指定部分局部发光效果

最终效果 寒冰法师 火焰法师 文章目录 最终效果寒冰法师火焰法师 素材一、功能分析实现方法基本思路Unity的Bloom后处理为什么关键部位白色&#xff1f;最终结果 二、 新建URP项目三、合并图片四、使用PS制作黑白图片方法一 手动涂鸦方法二 魔棒工具1. 拖入图片进PS&#xff0…...

Ubuntu 24.04 LTS Noble安装Docker Desktop简单教程

Docker 为用户提供了在 Ubuntu Linux 上快速创建虚拟容器的能力。但是&#xff0c;那些不想使用命令行管理容器的人可以在 Ubuntu 24.04 LTS 上安装 Docker Desktop GUI&#xff0c;本教程将提供用于设置 Docker 图形用户界面的命令…… Docker Desktop 是一个易于使用的集成容…...

XML 和 SimpleXML 入门教程

XML 和 SimpleXML 入门教程 XML&#xff08;可扩展标记语言&#xff09;是一种用于存储和传输数据的标记语言。它是一种自我描述的语言&#xff0c;允许用户定义自己的标签来表示数据。SimpleXML 是 PHP 中的一个扩展&#xff0c;用于解析和操作 XML 数据。本文将介绍 XML 和 …...

leetcode--链表类题目总结

本文作为刷题时对链表类题目的总结. 常见技巧: 引入虚拟头节点 便于处理边界情况便于对链表操作快慢双指针(判环,找环的入口等)链表逆序(推荐使用 虚拟头节点 头插法 进行逆序) 链表逆序( 头插法 虚拟头节点):链表内指定区间反转_牛客题霸_牛客网 虚拟节点:合并…...

打卡第22天------回溯算法

开始学习了,希望我可以尽快成功上岸! 一、回溯理论基础 什么是回溯法?回溯法也可以叫做回溯搜索法,它是一种搜索的方式。 回溯是递归的副产品,只要有递归就会有回溯。 回溯法的效率回溯法的本质是穷举,穷举所有可能,然后找出我们想要的答案。如果想让回溯法高效一些,可…...

Ubuntu对比两个文件内容有什么区别?

在Ubuntu&#xff08;或任何基于Linux的系统&#xff09;中&#xff0c;你可以使用多种命令行工具来比较两个文件的内容差异。以下是一些常用的方法&#xff1a; 1. **diff 命令**&#xff1a; diff 是Linux中用于比较两个文件差异的标准工具。它逐行比较文件&#xff0c;并显示…...

python:本机摄像头目标检测实时推理(使用YOLOv8n模型)

本文将介绍如何使用本机摄像头进行目标检测实时推理的python代码。 文章目录 一、下载YOLO权重文件二、环境配置三、完整代码 一、下载YOLO权重文件 https://github.com/ultralytics/ultralytics?tabreadme-ov-file 拉到网页最下面&#xff0c;选择适合的模型&#xff0c;下…...

Spark实时(四):Strctured Streaming简单应用

文章目录 Strctured Streaming简单应用 一、Output Modes输出模式 二、Streaming Table API 三、​​​​​​​​​​​​​​Triggers 1、​​​​​​​unspecified&#xff08;默认模式&#xff09; 2、​​​​​​​​​​​​​​Fixed interval micro-batches&am…...

SpringBoot上传超大文件导致OOM,完美问题解决办法

问题描述 报错: Caused by: java.lang.OutOfMemoryError at java.io.ByteArrayOutputStream.hugeCapacity(ByteArrayOutputStream.java:123) ~[?:1.8.0_381] at java.io.ByteArrayOutputStream.grow(ByteArrayOutputStream.java:117) ~[?:1.8.0_381] at java.…...

PyTorch 的各个核心模块和它们的功能

1. torch 核心功能 张量操作&#xff1a;PyTorch 的张量是一个多维数组&#xff0c;类似于 NumPy 的 ndarray&#xff0c;但支持 GPU 加速。数学运算&#xff1a;提供了各种数学运算&#xff0c;包括线性代数操作、随机数生成等。自动微分&#xff1a;torch.autograd 模块用于…...

Java开发之LinkedList源码分析

#来自ゾフィー&#xff08;佐菲&#xff09; 1 简介 LinkedList 的底层数据结构是双向链表。可以当作链表、栈、队列、双端队列来使用。有以下特点&#xff1a; 在插入或删除数据时&#xff0c;性能好&#xff1b;允许有 null 值&#xff1b;查询效率不高&#xff1b;线程不安…...

外卖霸王餐系统架构怎么选?

在当今日益繁荣的外卖市场中&#xff0c;外卖霸王餐作为一种独特的营销策略&#xff0c;受到了众多商家的青睐。然而&#xff0c;要想成功实施外卖霸王餐活动&#xff0c;一个安全、稳定且高效的架构选择至关重要。本文将深入探讨外卖霸王餐架构的选择&#xff0c;以期为商家提…...

AV1技术学习:Transform Coding

对预测残差进行变换编码&#xff0c;去除潜在的空间相关性。VP9 采用统一的变换块大小设计&#xff0c;编码块中的所有的块共享相同的变换大小。VP9 支持 4 4、8 8、16 16、32 32 四种正方形变换大小。根据预测模式选择由一维离散余弦变换 (DCT) 和非对称离散正弦变换 (ADS…...

Git操作指令

Git操作指令 一、安装git 1、设置配置信息&#xff1a; # global全局配置 git config --global user.name "Your username" git config --global user.email "Your email"2、查看git版本号 git -v # or git --version3、查看配置信息&#xff1a; git…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...