深入理解数据结构第二弹——二叉树(2)——堆排序及其时间复杂度

看这篇前请先把我上一篇了解一下:深入理解数据结构第一弹——二叉树(1)——堆-CSDN博客

前言:

相信很多学习数据结构的人,都会遇到一种情况,就是明明最一开始学习就学习了时间复杂度,但是在后期自己写的程序或者是做到哪个需要判断时间复杂度的题时,仍然判断不出来时间复杂度是多少,今天,我们结合我们上期学习的堆,给大家深入剖析一下时间复杂度这个概念,同时更深入的理解堆的概念,方便我们后期应用堆进行排序等。

目录

一、堆排序

1、堆排序的大体思路

2、堆排序的实例讲解

二、堆排序的时间复杂度

向下排序的时间复杂度

向上排序的时间复杂度

堆排序整体的时间复杂度

总结


一、堆排序

1、堆排序的大体思路

在上一篇我们已经讲过了堆是什么东西,我们已经知道堆有大堆和小堆两种形式,堆排序的想法正是借助它的这个特点诞生的,例如:

数组 { 7,8 ,3 ,5 ,1 ,9 ,5 ,4}在堆中分布为:

如图展示的是小堆,首先我们先强调一点,降序是需要小堆来解决,升序是需要大堆来解决

比如说图上这个数组,我们要求它的降序序列时,因为堆顶元素一定是堆中最小的,所以我们就可以把堆顶元素与堆尾元素进行交换,然后把堆尾元素刨除在外再进行降序排列

2、堆排序的实例讲解

堆排序与堆相比并没有什么新东西,把我前面那章看明白,这里直接把代码呈上

(除了test.c)其他的是直接从上一章搬过来的

Seqlist.h

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int sz;
	int capacity;
}HP;
 
//初始化
void HeapInit(HP* php);
//销毁
void HeapDestory(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//找堆顶元素
HPDataType HeapTop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//算个数
int HeapSize(HP* php);

test.c

//堆排序
void HeapSort(int* a, int n)
{
	//建堆——向下调整建堆O(N-log(n))
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);

		//再调整,选出次小数
		AdjustDown(a, end, 0);
		end--;
	}
}
int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));
	return 0;
}

Seqlist.c

//堆
//初始化
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->sz = 0;
}
//销毁
void HeapDestory(HP* php)
{
	free(php->a);
	free(php);
}
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//删除
 
//向上调整(小堆)
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
 
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child<n)
	{
		if (child+1<n&&a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
//插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->sz == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->sz] = x;
	php->sz++;
 
	//向上调整
	AdjustUp(php->a, php->sz - 1);
}
//删除
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->sz - 1]);
	php->sz--;
	//向下调整
	AdjustDown(php->a, php->sz,0);
}
//判断是否为空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->sz == 0;
}
//找堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}
//算个数
int HeapSize(HP* php)
{
	assert(php);
	return php->sz;
}

实现上述代码,我们就可以实现堆排序了

二、堆排序的时间复杂度

我们都知道在实现堆时有向上排序和向下排序两种,细心的人可能已经注意到,我在实现上面那个堆排序用例时,用的是向下排序,原因就是向下排序的时间复杂度更低,接下来,我们就来分析一下这两种排序各自的时间复杂度

向下排序的时间复杂度

向上排序的时间复杂度

堆排序整体的时间复杂度

计算堆排序整体的时间复杂度就是计算上面这两步的时间复杂度

第一步:

因为这一步实际上就是多次向下调整建堆,所以这一步时间复杂度就是向下调整法时间复杂度的倍数,那根据渐进表示法就可以表示为O(N-log(N)),因为当N很大时,log(N)比N小很多,所以可以忽略表示为O(N)

第二步:

第二步外循环需要N次,内循环看似每次都是一个完整的向下排序法,但其实随着循环次数的增加,里面向下排序的时间复杂度在不断减小,因为堆尾排过去的数字实际上就不用再参与堆排序的,所以这一步时间复杂度实际上是O(N*log)

因此,堆排序的时间复杂度为O(N+N*log(N))

总结

堆排序及其时间复杂度的讲解就到此为止了,如果有不理解的地方欢迎在评论区中指出或者与我私信交流,欢迎各位大佬来访!!!

创作不易,还请各位大佬点赞支持!!!

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

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

相关文章

电商-广告投放效果分析(KMeans聚类、数据分析-pyhton数据分析

电商-广告投放效果分析&#xff08;KMeans聚类、数据分析&#xff09; 文章目录 电商-广告投放效果分析&#xff08;KMeans聚类、数据分析&#xff09;项目介绍数据数据维度概况数据13个维度介绍 导入库&#xff0c;加载数据数据审查相关性分析数据处理建立模型聚类结果特征分析…

Ceph学习 - 1.存储知识

文章目录 1.存储基础1.1 基础知识1.1.1 存储基础1.1.2 存储使用 1.2 文件系统1.2.1 简介1.2.2 数据存储1.2.3 存储应用的基本方式1.2.4 文件存储 1.3 小结 1.存储基础 学习目标&#xff1a;这一节&#xff0c;我们从基础知识、文件系统、小节三个方面来学习。 1.1 基础知识 1.…

day01 51单片机

51单片机学习 1 51单片机概述 1.1 51单片机简介 目前使用的51单片机一般是宏晶STC89系列,这其中流传最广的版本,也是我们课程的主角,就是STC89C52RC。 1.2 命名规则 1.3 单片机最小应用系统 2 点亮LED灯 2.1 硬件原理图 这个原理图非常简单,VCC接保护电阻R1,串联LED1最…

IOTX:未来市场爆发点的RWA协议?DePIN赛道被低估的龙头

从基本面来看&#xff0c;IoTeX的目标是创建一个连接的世界&#xff0c;在这个世界中&#xff0c;每个人都能控制自己的数据、设备和身份。通过区块链技术&#xff0c;IoTeX旨在解锁智能设备和数据的潜力&#xff0c;支持新一代的现实世界Dapp和数字资产的发展。IOTX始终致力于…

个性化内容的力量:Kompas.ai如何帮你定制内容

在当今的数字化营销环境中&#xff0c;个性化内容已经成为品牌与消费者建立深层次联系的关键。个性化内容不仅能够更好地满足用户的需求&#xff0c;还能够加深用户的品牌体验&#xff0c;从而提高用户满意度和忠诚度。本文将深入探讨个性化内容在提升用户参与度和忠诚度方面的…

Incus:新一代容器与虚拟机编排管理引擎

Incus是什么&#xff1f; Incus是一个用于编排管理应用型容器、系统型容器及虚拟机实例的管理工具。它是对 Canonical LXD 的继承与发展&#xff0c;引入了更多的存储驱动支持。 Incus项目的产品地址&#xff1a;Linux Containers - Incus - Introduction 在 LXC-Incus 项目…

Java练习

这个练习我用到了继承&#xff0c;多态和封装。 1.继承&#xff1a; Animal 类是一个抽象类&#xff0c;它有两个子类 Dog 和 Cat。 Dog 和 Cat 分别继承自 Animal 类&#xff0c;因此它们可以使用 Animal 类中定义的属性和方法&#xff0c;同时也可以有自己特有的属性和方法。…

鸿蒙OS元服务开发:【(Stage模型)学习窗口沉浸式能力】

一、体验窗口沉浸式能力说明 在看视频、玩游戏等场景下&#xff0c;用户往往希望隐藏状态栏、导航栏等不必要的系统窗口&#xff0c;从而获得更佳的沉浸式体验。此时可以借助窗口沉浸式能力&#xff08;窗口沉浸式能力都是针对应用主窗口而言的&#xff09;&#xff0c;达到预…

基于springboot+vue+Mysql的教学视频点播系统

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…

pymc,一个灵活的的 Python 概率编程库!

目录 前言 安装与配置 概率模型 贝叶斯推断 概率分布 蒙特卡罗采样 贝叶斯网络 实例分析 PyMC库的应用场景 1. 概率建模 2. 时间序列分析 3. 模式识别 总结 前言 大家好&#xff0c;今天为大家分享一个超强的 Python 库 - pymc Github地址&#xff1a;https://gith…

黄金票据攻击

黄金票据攻击——域内横向移动技术 一、黄金票据攻击介绍&#xff1a; 黄金票据攻击是一种滥用Kerberos身份认证协议的攻击方式&#xff0c;它允许攻击者伪造域控krbtgt用户的TGT&#xff08;Ticket-Granting Ticket&#xff09;。通过这种方法&#xff0c;攻击者可以生成有效…

怎么禁止特定程序运行

计算机已经成为了人们日常生活和工作中不可或缺的工具。 然而&#xff0c;随着计算机应用的广泛化&#xff0c;如何管理和控制计算机上的程序运行也成为了一个亟待解决的问题。 特别是在企业、学校或一些需要严格控制计算机使用环境的场所。 为什么要禁止特定程序运行&#x…

Catcatcat【杂项 攻防世界】

知识点&#xff1a; strings 命令 打印文件中可以打印的字符&#xff0c;可以是任意文件grep flag 过滤出文件中的flag关键字rabbit加密 深入了解Rabbit加密技术&#xff1a;原理、实现与应用-CSDN博客对称加密算法需要密钥&#xff0c;也可不设置数据开头固定&#xff1a;U2F…

6.8物联网RK3399项目开发实录-驱动开发之RTC实时时钟的使用(wulianjishu666)

90款行业常用传感器单片机程序及资料【stm32,stc89c52,arduino适用】 链接&#xff1a;https://pan.baidu.com/s/1M3u8lcznKuXfN8NRoLYtTA?pwdc53f RTC 使用 简介 AIO-3399J 开发板上有 一个集成于 RK808 上的RTC(Real Time Clock)&#xff0c;主要功能有时钟&#xff0c…

【OpenCV-颜色空间】

OpenCV-颜色空间 ■ RGB■ BGR■ HSV■ HSL■ HUE■ YUV ■ RGB ■ BGR BGR 就是RGB R和B调换位置。 OpenCV 默认使用BGR ■ HSV ■ HSL ■ HUE ■ YUV

【高校科研动态】贵州师大博士生封清为一作在J. Clean. Prod.发文:中国扶贫搬迁对生态影响的量化研究——以贵州省为例

目录 1.文章简介 2.主要研究内容 3.文章引用 1.文章简介 论文名称&#xff1a;Quantifying the extent of ecological impact from Chinas poverty alleviation relocation program: A case study in Guizhou Province 第一作者及通讯作者&#xff1a;封清&#…

代码随想录第28天 | 93.复原IP地址 、 78.子集 、 90.子集II

一、前言&#xff1a; 参考文献&#xff1a;代码随想录 今天的主题内容是回溯算法&#xff0c;这一章的干货很多&#xff0c;我需要慢慢的品味&#xff0c;不单单只是表象&#xff0c;还需要研究深层原理。 二、复原IP地址 1、思路&#xff1a; &#xff08;1&#xff09;…

反射的学习

反射的作用&#xff1a; 1.获取一个类里面的所有信息&#xff0c;获取到之后&#xff0c;在执行其他的业务逻辑 2.结合配置文件&#xff0c;动态的创建对象并调用方法

OpenHarmony实战:轻量级系统之启动恢复子系统移植

启动恢复子系统负责在内核启动之后到应用启动之前的系统关键进程和服务的启动过程的功能。 移植指导 针对轻量系统主要提供了各服务和功能的启动入口标识。在SAMGR启动时&#xff0c;会调用bootstrap标识的入口函数&#xff0c;并启动系统服务。 适配完成后&#xff0c;调用…

Node.js------Express

◆ 能够使用 express.static( ) 快 速 托 管 静 态 资 源◆ 能够使用 express 路 由 精 简 项 目 结 构◆ 能够使用常见的 express 中间件◆ 能够使用 express 创建API接口◆ 能够在 express 中启用cors跨域资源共享 一.初识Express 1.Express 简介 官方给出的概念&#xff…