数据结构:堆的应用
堆排序
假定有一组数据极多的数,让我们进行排序,那我们很容易想到一种经典的排序方法,冒泡排序,我们对冒泡排序的时间复杂度进行分析:

显然,冒泡排序的时间复杂度是O(n^2),当数据量巨大时,冒泡排序需要比较长时间才能完成排序,这在实际应用中是没有意义的。
而相比之下的堆排序时间开销则小得多。
接下来先给出堆排序的代码:
void Swap(int* child, int* parent)
{int tem = *child;*child = *parent;*parent = tem;
}void DownAdjust(int* p,int size,int parent)
{int child = parent * 2 + 1;while (child<size){if (child<size-1 && p[child + 1] < p[child])//size-1,不是size++child;if (p[child] < p[parent]){Swap(&p[child], &p[parent]);//parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
void HeapSort(int* p, int size)
{//1.建堆//先找到最后一个非叶子节点,然后逆序向下调整for (int i = (size - 1 - 1) / 2; i >= 0; i--){DownAdjust(p, size, i);}//2.对堆排序int end = size - 1;while (end>0){Swap(&p[0], &p[end]);DownAdjust(p, end, 0);--end;}
}
我们知道堆在逻辑上是完全二叉树,在物理上是数组,那么给一个很大的数组,我们完全对这个数组进行建堆,然后进行堆排序。
接下来对堆排序的时间复杂度进行分析:
一个程序的时间复杂度看的是执行次数最多的基本语句,因此看建堆的时间复杂度即可:

因此,时间复杂度为O(n)
两者对比我们发现,堆排序显然是更优的。
我们可以看看运行实例:
冒泡排序:

堆排序:

可以看出,堆排序的优越性。
相关文章:
数据结构:堆的应用
堆排序 假定有一组数据极多的数,让我们进行排序,那我们很容易想到一种经典的排序方法,冒泡排序,我们对冒泡排序的时间复杂度进行分析: 显然,冒泡排序的时间复杂度是O(n^2),当数据量…...
Spring Boot 实现文件分片上传和下载
文章目录 一、原理分析1.1 文件分片1.2 断点续传和断点下载1.2 文件分片下载的 HTTP 参数 二、文件上传功能实现2.1 客户端(前端)2.2 服务端 三、文件下载功能实现3.1 客户端(前端)3.2 服务端 四、功能测试4.1 文件上传功能测试4.2 文件下载功能实现 参考资料 完整案例代码&…...
夹逼准则求数列极限(复习总结)
记住这两个准则,然后我们就开始看题目 因为是证明题,所以要放缩到什么值已经是确定的了。也就是放缩到0,然后很明显地可以看出前面已经有一个可以使得极限是0了,并且后面的值明显小于1,就是逐渐缩小的趋势,…...
【python】OpenCV—WaterShed Algorithm(1)
文章目录 1、功能描述2、代码实现3、完整代码4、效果展示5、涉及到的库函数5.1、cv2.pyrMeanShiftFiltering5.2、cv2.morphologyEx5.3、cv2.distanceTransform5.4、cv2.normalize5.5、cv2.watershed 6、参考 1、功能描述 基于分水岭算法对图片进行分割 分水岭分割算法&#x…...
查找与排序-插入排序
思考:在把待排序的元素插入已经有序的子序列中时,是不是一定要逐一比较?有没有改进方法? 在查找插入位置的时候可以采用折半(二分)搜索的办法。 一、折半插入排序 1.折半插入排序算法的基本思想 假设待…...
JAVA基础:多线程 (学习笔记)
多线程 一,什么是线程? 程序:为完成特定任务、用某种语言编写的一组指令的集合,是一段静态的代码进程:程序的一次执行过程。 正在运行的一个程序,进程作为资源分配的单位,在内存中会为每个进程分配不同的…...
盲盒小程序/APP系统,市场发展下的新机遇
当下,年轻人热衷于各种潮玩商品,尤其是一盲盒为主的潮流玩具风靡市场,吸引了众多入局者。随着互联网信息技术的快速发展,各类线上盲盒小程序又进一步推动了盲盒市场的发展,成为年轻人拆盲盒的主要阵地。在盲盒经济中&a…...
Unity3D LayoutGroup组件详解
Unity3D中的LayoutGroup组件是一种强大的工具,用于动态调整UI元素的布局。它主要包括三种类型:Horizontal Layout Group(水平布局组)、Vertical Layout Group(垂直布局组)和Grid Layout Group(网…...
[NeetCode 150] Foreign Dictionary
Foreign Dictionary There is a foreign language which uses the latin alphabet, but the order among letters is not “a”, “b”, “c” … “z” as in English. You receive a list of non-empty strings words from the dictionary, where the words are sorted lex…...
小新学习K8s第一天之K8s基础概念
目录 一、Kubernetes(K8s)概述 1.1、什么是K8s 1.2、K8s的作用 1.3、K8s的功能 二、K8s的特性 2.1、弹性伸缩 2.2、自我修复 2.3、服务发现和负载均衡 2.4、自动发布(默认滚动发布模式)和回滚 2.5、集中化配置管理和密钥…...
如何用终端批量修改一个文件夹里面所有图片的后缀名?
步骤: winr ,然后输入cmd,打开终端 使用cd命令导航到要修改图片后缀名的文件夹。eg.我的该文件夹(C:\dog)下,保存的图片。(cd和文件目录之间要有空格)批量改变后缀名,假如让后缀名全部要从 ".webp&q…...
关于AI网络架构的文章
思科OCP anounce了800G 51.2T G200-based minipack3 switch。对比之前Tesla anounce的TTPoE。真的很好奇,谁是AI-networking的未来,以及思科是否走在正确的路上,以及S1背后的技术。 大致浏览了相关的文章,先mark住,回…...
【ChatGPT】在多轮对话中引导 ChatGPT 保持一致性
在多轮对话中引导 ChatGPT 保持一致性 多轮对话是与 ChatGPT 等对话模型互动时的一大特点,特别是在复杂任务和长时间对话中,保持对话的一致性显得尤为重要。用户往往希望 ChatGPT 能够在上下文中理解先前的对话内容,避免反复重申问题或者给出…...
【Chapter 7】因果推断中的机器学习:从T-学习器到双重稳健估计
随着机器学习技术的发展,数据科学家们开始探索如何将这些先进的方法应用于因果推断问题,尤其是处理异质性效应(Effect Heterogeneity)时。本章将介绍几种基于机器学习的因果推断方法,包括T-学习器、X-学习器和双重稳健…...
vim的使用方法
常见的命令可参考: Linux vi/vim | 菜鸟教程www.runoob.com/linux/linux-vim.html编辑https://link.zhihu.com/?targethttps%3A//www.runoob.com/linux/linux-vim.html 1. vim的工作模式 vi/vim 共分为三种模式,命令模式、编辑输入模式和末行&am…...
OPPO携手比亚迪共同探索手机与汽车互融新时代
10月23日,OPPO与比亚迪宣布签订战略合作协议,双方将共同推进手机与汽车的互融合作,这一合作也标志着两大行业巨头在技术创新和产业融合上迈出了重要一步,为手机与汽车的深度融合探索新的可能。 OPPO创始人兼首席执行官陈明永、OP…...
Apache Linkis:重新定义计算中间件
在大数据技术蓬勃发展的今天,我们见证了从单一计算引擎到多元化计算范式的演进。然而,随着企业数据应用场景的日益丰富,一个严峻的挑战逐渐显现:如何有效管理和协调各类计算引擎,使其能够高效协同工作?Apac…...
go gorm简单使用方法
GORM 是 Go 语言中一个非常流行的 ORM(对象关系映射)库,它允许开发者通过结构体来定义数据库表结构,并提供了丰富的 API 来操作数据库。 安装 go get -u gorm.io/gorm go get -u gorm.io/driver/sqlite表结构 在 gorm 中定义表结…...
【c++高级篇】--多任务编程/多线程(Thread)
目录 1.进程和线程的概念: 1.1 进程(Process): 1.2线程(Thread): 1.3 对比总结: 2.多线程编程: 2.1 基于线程的多任务处理(Thread)…...
【力扣专题栏】两数相加,如何实现存储在链表中的整数相加?
题解目录 1、题目描述解释2、算法原理解析3、代码编写(原始版本)4、代码编写(优化版本) 1、题目描述解释 2、算法原理解析 3、代码编写(原始版本) /*** Definition for singly-linked list.* struct ListN…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
