【数据结构】--- 堆的应用

 

 个人主页:星纭-CSDN博客

系列文章专栏 :数据结构

踏上取经路,比抵达灵山更重要!一起努力一起进步!

一.堆排序 

 在前一个文章的学习中,我们使用数组的物理结构构造出了逻辑结构上的堆。那么堆到底有什么用呢???

首先思考这样一个问题,假设给定一个随机的数组,如何将这个数组建堆(在不使用额外的空间的条件下)。

这个问题不难,只需用到向上调整算法即可。

int main()
{int a[] = { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 };int i = 1;for (i = 1; i < sizeof(a) / sizeof(a[0]); i++) {AdjustUp(a, i);}return 0;
}

通过调试不难发现此时已经是一个大堆了。

如果想要得到小堆,只需要更改向上调整函数即可。

得到了大堆之后,又如何将这个数组排序得到一个升序的数组呢???

因为在大堆中,堆顶的数据一定是最大的,可以先将堆顶数据和数组最后一个位置上的数据进行交换,不管此时最大的数据,只看前size-1这个数据,进行向下调整得到第二大的数据,再更倒数第二个位置上的数据进行交换,..........依次进行下去就会得到一个升序的数组。 

int main()
{int a[] = { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 };int i = 1;for (i = 1; i < sizeof(a) / sizeof(a[0]); i++) {AdjustUp(a, i);}int end = sizeof(a) / sizeof(a[0]) - 1;while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}return 0;
}

简单来说,升序,建大堆,降序,建小堆。这就是堆排序。

然后就是向下调整建堆。假设给定一个数组,使用二叉树的形式表示,如下图所示 

假设这个二叉树,对于根来说,其左子树是大堆,右子树也是大堆,而这整个二叉树并不是大堆,我们就可以使用向下调整来使其变成大堆。可是这样一个随机的数组肯定是不满足上述的条件的,那么该如何使用向下调整算法来使其变成大堆呢?

答案就是倒着调整。

假设我们从最后一个数据开始,一个节点是既可以看作大堆也可以看作小堆的,此时我们就不需要对其进行调整,对于完全二叉树来说,他的叶子节点都不需要调整,所以我们就需要调整倒数第一个非叶子节点。以上图举例,也就是第三层第二个节点,将它和它的孩子节点看作一个树,这样就可以调整了。

那么倒数第一个非叶子节点的下标该怎么求呢?

倒数第一个非叶子节点是最后一个节点父亲节点。而最后一个节点的下标是n-1。所以倒数第一个非叶子节点的下标就是(n-1-1)/ 2;

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

二.建堆的时间复杂度

既然有两种不同的建堆算法,那么采用哪一种算法来建堆是更加好的呢?

所以接下来算一算两个算法的时间复杂度 

对于一个完全二叉树而言,假设其高度是h,那么它的节点个数最少和最多情情况,分别是最后一层只有一个节点和一个满二叉树。

对于一个满二叉树来说总节点个数n和高度h的关系是

F(n) = 2^0 + 2^1 + 2^2 + ... + 2^(h-1) = 2^h - 1。

h = log2(n + 1)

对于最后一层只有一个节点的二叉树而言总节点个数和高度h的关系是

F(n) = 2^0 + 2^1 + 2^2 + ... + 2^(h-2) + 1 = 2^(h-1) - 1 + 1= 2^(h-1)。

h = log2(n) - 1

根据大O的渐进表示法,我们可以大致得到h = logN的。

这样我们就得到了h和N之间的关系。

1.向上调整

计算向上调整的时间复杂度,我们需要计算总共向上调整了几次。

T(h) = 2^1*1 + 2^2 * 2 + ... + 2^(h-2)*(h-2) + 2^(h-1)*(h-1).
2*T(h) =       2^2*1 + 2^3 * 2 + ... +         2^(h-1)*(h-2) + 2^h*(h-1).
-T(h) = 2^1 + 2^2 + ... +2^(h-1) - 2^h*(h-1).= 2^h  - 2 -2^h*(h-1)= 2^h(1-h+1) -2 T(h) = 2 + 2 ^ h * hT(N) = 2 + 2 * log(N) * N = O(N * logN)

向上调整的时间复杂度是N*logN.

2.向下调整

T(h) = 2^0*(h-1) + 2^1*(h-2) + ...             +2^(h-2) * 1
2 * T(h) =         2^1*(h-1) + 2^2*(h-2) + ... +2^(h-2) * 2+2^(h-1) * 1
T(h) = 2^1 + 2^2+...+2^(h-2) +2^(h-1) - (h-1)= 2^h - 2 - h + 1= 2^h - h - 1= N - logN - 1= O(N)

对比不难发现向下调整的时间复杂度算法更优。 

三.TopK问题

 TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
    比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
    前k个最大的元素,则建小堆
    前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素    
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

利用此算法的时间复杂度是O(N)

 

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

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

相关文章

【Linux】01.Linux 的常见指令

1. ls 指令 语法&#xff1a;ls [选项] [目录名或文件名] 功能&#xff1a;对于目录&#xff0c;该命令列出该目录下的所有子目录与文件。对于文件&#xff0c;将列出文件名以及其他信息 常用选项&#xff1a; -a&#xff1a;列出当前目录下的所有文件&#xff0c;包含隐藏文件…

Spring webflux基础核心技术

一、 用操作符转换响应式流 1 、 映射响应式流元素 转换序列的最自然方式是将每个元素映射到一个新值。 Flux 和 Mono 给出了 map 操作符&#xff0c;具有 map(Function<T&#xff0c;R>) 签名的方法可用于逐个处理元素。 当操作符将元素的类型从 T 转变为 R 时&#xf…

「豆包Marscode体验官」我用豆包Marscode画数据大屏

认识豆包Marscode 豆包 MarsCode IDE 是一个 AI 原生的云端集成开发环境&#xff08;IDE&#xff09;。内置的 AI 编程助手和开箱即用的开发环境让我们可以更加专注于各种项目的开发。豆包 MarsCode 编程助手&#xff0c;具备以智能代码补全为代表的 AI 功能。支持了多种编程语…

【学习笔记】无人机(UAV)在3GPP系统中的增强支持(十二)-无人机群在物流中的应用

引言 本文是3GPP TR 22.829 V17.1.0技术报告&#xff0c;专注于无人机&#xff08;UAV&#xff09;在3GPP系统中的增强支持。文章提出了多个无人机应用场景&#xff0c;分析了相应的能力要求&#xff0c;并建议了新的服务级别要求和关键性能指标&#xff08;KPIs&#xff09;。…

解读网传《深圳IT圈⭕新解读八小时工作制》

网传深圳IT圈的新解读八小时工作制 工作时间安排&#xff1a; 10:00-12:0014:00-18:0019:00-21:00 初看&#xff1a;有惊喜 上午开始时间晚&#xff1a;相对于传统的9点开始&#xff0c;这种安排允许员工有更多的早晨时间&#xff0c;可以用来休息或处理个人事务。下午和晚上分…

Amazon EC2 部署Ollama + webUI

最近和同事闲聊&#xff0c;我们能不能内网自己部署一个LLM&#xff0c;于是便有了Ollama webUI的尝试 对于Linux&#xff0c;使用一行命令即可 curl -fsSL https://ollama.com/install.sh | shollama --help Large language model runnerUsage:ollam…

架构设计-NX的二次开发API架构设计介绍

1.与整体的关系 2.API设计目标 能够允许用户访问NX的所有UI工具组件&#xff0c;二次开发用户能够编写外观和运行行为类似NX的应用程序。能够允许用户直接访问NX数据模型即使底层数据结构和功能实现发生很大变化&#xff0c;API接口保持稳定&#xff0c;不会影响上层用户。 3…

智能家居开发新进展:乐鑫 ESP-ZeroCode 与亚马逊 ACK for Matter 实现集成

日前&#xff0c;乐鑫 ESP-ZeroCode 与亚马逊 Alexa Connect Kit (ACK) for Matter 实现了集成。这对智能家居设备制造商来说是一项重大进展。开发人员无需编写固件或开发移动应用程序&#xff0c;即可轻松设计符合 Matter 标准的产品。不仅如此&#xff0c;开发者还可以在短短…

网络协议 — Keepalived 高可用方案

目录 文章目录 目录Keepalived 是实现了 VRRP 协议的软件Keepalived 的软件架构VRRP StackCheckersKeepalived 的配置Global configurationvrrp_scriptVRRP Configurationvrrp synchroization groupvrrp instancevirtual ip addressesvirtual routesLVS Configurationvirtual_s…

知识图谱与LLMs:实时图分析(通过其关系的上下文理解数据点)

大型语言模型 (LLM) 极大地改变了普通人获取数据的方式。不到一年前&#xff0c;访问公司数据需要具备技术技能&#xff0c;包括熟练掌握各种仪表板工具&#xff0c;甚至深入研究数据库查询语言的复杂性。然而&#xff0c;随着 ChatGPT 等 LLM 的兴起&#xff0c;随着所谓的检索…

不常用的第三方服务集成

1.ldap 1.1.ldap服务搭建 docker方式搭建:包含了ldap服务和ldap admin图形化界面服务 参考ldap服务:http://127.0.0.1:81 用户名:CN=admin,DC=ldap,DC=com 密码:123456 docker-compose.yml文件内容如下 version: 3services:ldap:image: osixia/openldap:latestcontainer…

0基础学会在亚马逊云科技AWS上利用SageMaker、PEFT和LoRA高效微调AI大语言模型(含具体教程和代码)

项目简介&#xff1a; 小李哥今天将继续介绍亚马逊云科技AWS云计算平台上的前沿前沿AI技术解决方案&#xff0c;帮助大家快速了解国际上最热门的云计算平台亚马逊云科技AWS上的AI软甲开发最佳实践&#xff0c;并应用到自己的日常工作里。本次介绍的是如何在Amazon SageMaker上…

【qt】TCP客户端如何断开连接?

disconnectFromHost() 来关闭套接字,断开连接. 当我们关闭窗口时,也需要断开连接. 需要重写关闭事件 如果当前的套接字状态是连接上的,我们就可以来断开连接. 运行结果:

SSM框架学习笔记(仅供参考)

&#xff08;当前笔记简陋&#xff0c;仅供参考&#xff09; 第一节课&#xff1a; &#xff08;1&#xff09;讲述了Spring框架&#xff0c;常用jar包&#xff0c;以及框架中各个文件的作用 &#xff08;2&#xff09;演示了一个入门程序 &#xff08;3&#xff09;解释了…

前端项目本地的node_modules直接上传到服务器上无法直接使用(node-sasa模块报错)

跑 jekins任务的服务器不能连接外网下载依赖包&#xff0c;就将本地下载的 node_modules直接上传到服务器上&#xff0c;但是运行时node-sass模块报错了ERROR in Missing binding /root/component/node_modules/node-sass/vendor/linux-x64-48/binding.node >> 报错信息类…

不会编程怎么办?量化交易不会编程可以使用吗?

量化交易使用计算机模型程序代替人工进行交易&#xff0c;一般需要投资者自己编写程序建模&#xff0c;然后回测无误之后再进行实盘交易&#xff0c;那么不会编程的投资者能使用量化软件进行量化交易吗&#xff1f; 不会编程使用量化软件有两种方法 一种是请人代写代码&#x…

浅谈后置处理器之JSON提取器

浅谈后置处理器之JSON提取器 JMeter 的 JSON 提取器&#xff08;JSON Extractor&#xff09;是一个强大的后置处理器&#xff0c;它允许用户从HTTP响应、数据库查询或其他类型的响应中提取JSON数据&#xff0c;并将这些数据存储为变量&#xff0c;以便在后续的请求中重用。这对…

LabVIEW人工模拟肺控制系统开发

开发了一种创新的主被动一体式人工模拟肺模型&#xff0c;通过LabVIEW开发的上位机软件&#xff0c;实现了步进电机驱动系统的精确控制和多种呼吸模式的模拟。该系统不仅能够在主动呼吸模式下精确模拟快速呼吸、平静呼吸和深度呼吸&#xff0c;还能在被动模式下通过PID控制实现…

LeetCode加油站(贪心算法/暴力,分析其时间和空间复杂度)

题目描述 一.原本暴力算法 最初的想法是&#xff1a;先比较gas数组和cost数组的大小&#xff0c;找到可以作为起始点的站点(因为如果你起始点的油还不能到达下一个站点&#xff0c;就不能作为起始点)。当找到过后&#xff0c;再去依次顺序跑一圈&#xff0c;如果剩余的油为负数…

【代码随想录】【算法训练营】【第64天】 [卡码117]软件构建 [卡码47]参加科学大会

前言 思路及算法思维&#xff0c;指路 代码随想录。 题目来自 卡码网。 day 64&#xff0c;周三&#xff0c;继续ding~ 题目详情 [卡码117] 软件构建 题目描述 卡码117 软件构建 解题思路 前提&#xff1a; 思路&#xff1a; 重点&#xff1a; 代码实现 C语言 [卡码…