【数据结构】排序效率最优解之一：二叉树-堆

Hello everybody!今天打算给大家介绍一个功能比较强大的数据结构的基础，它不仅具有很高的应用价值而且排序效率很高。冒泡排序都知道叭，它的时间复杂度为O(n^2)，而堆排序的时间复杂度为O(n*logn)。堆排序直接碾压冒泡排序。在c语言阶段，我曾给过大家qsort函数模拟实现的代码，我是以冒泡排序为底层逻辑实现的：时间复杂度为O(n^2)。而真正库文件中的qsort是以快排为底层逻辑实现的：时间复杂度为O(n*logn)。所以当我们排较长的数值时，肉眼可见的会发现自己模拟实现的qsort的效率远远不及库文件中的qsort。这就很好的体现了时间复杂度为O(n*logn)的数据结构的魅力所在！那好，废话不多说，我们直接开始叭！

1.二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1.顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.链式存储

二叉树的链式存储结构是指，用链表来表示一颗二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链。在当前的知识将借助一般都是二叉链，后面的高阶数据结构如红黑树等会用到三叉链。

2.堆的基本结构

注意堆有大堆和小堆之分。

小堆：每个结点上的数据都比子结点上的数据小，故根结点为最小值。

大堆：每个结点上的数据都比子结点上的数据小，故根结点为最大值。

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int HPDataType;
typedef struct Heap {
	HPDataType* a;
	int size;
	int capacity;
}HP;

这是堆的结构。其中a为数组名，堆上的数全部存放在这个数组中。虽然用数组存放堆，但它们的逻辑结构为堆。

因为：每个父结点的下标*2+1得到其左边的子结点，父结点的下标*2+2得其右边得子结点。

当然也可以反过来推：不管是左边的子结点还是右边的子节点，它们的下标-1与2取整即可得到其父结点。因为小数部分会被省略！

void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);//插入数据并向上调整调整
void HeapPop(HP* php);//删除堆顶（根节点）

int HeapSize(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);

这些是堆需要实现的一些接口。其中最核心的是HeapPush和HeapPop，因为涉及到数据的调整。

其他接口就比较简单，我也就简单介绍一下。

3.接口的实现

那我就按照小堆给大家实现叭！

3.1初始化&销毁

void HeapInit(HP* php) {
	assert(php);//检查php是否为空指针
	php->a = NULL;
	php->size = php->capacity = 0;
}

void HeapDestroy(HP* php) {
	assert(php);
	free(php->a);//将a指向的动态空间还给操作系统
	php->a = NULL;//置空，避免出现野指针
	php->size = php->capacity = 0;
}

这两个接口比较简单，给出的注释比较详细。我就不过多赘述了！

3.2插入数据

void Swap(HPDataType* p1, HPDataType* p2) {
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType* a, HPDataType child) {
	int parent = (child - 1) / 2;//找父结点
	while (child > 0) {
		if (a[child] < a[parent]) {//当子结点小于父节点时，交换
			Swap(&a[child], &a[parent]);
			child = (child - 1) / 2;//找上一个子节点
			parent = (parent - 1) / 2;//找上一个父节点
		}
		else {
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x) {
	assert(php);
	if (php->size == php->capacity) {
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;//当容量等于有效数据时，按二倍扩容
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);//动态开辟空间
		assert(tmp);//检查是否开辟成功
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);//向上调整
}

我大概说一下这个接口的思路：1.首先看到HeapPush,先检查动态数组的容量是否够用，不够用的话就扩容。检查容量过后进入AdjustUp

2.在AdjustUp中，可以通过子节点找父节点，如果不满足小堆的规则，那么父节点的数值和子节点的数值交换，然后下标继续向上调整。直到子节点的下标为零（到达根结点时）结束。

通过调试会发现，确实是一个堆，这个接口的功能正常。

3.3删除堆顶

void AdjustDown(HPDataType* a, int size, int parent) {
	int child = parent * 2 + 1;//通过根结点找子结点
	while (child<size) {
		if (child + 1 < size && a[child + 1] < a[child]) {//如果左孩子大于右孩子，用右孩子
			child++;
		}
		if (a[parent] > a[child]) {
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;//继续向下调整
		}
		else {
			break;
		}
	}
}

void HeapPop(HP* php) {
	assert(php);//检查指针
	assert(php->size > 0);//检查有效数据
	Swap(&php->a[0], &php->a[php->size - 1]);//头尾数值交换
	php->size--;//删除最后一个
	AdjustDown(php->a, php->size, 0);//根结点向下调整
}

3.4结点个数&访问根节点&判空

HPDataType HeapTop(HP* php) {
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

int HeapSize(HP* php) {
	assert(php);
	return php->size;
}

bool HeapEmpty(HP* php) {
	assert(php);
	return php->size == 0;
}

这三个接口就很简单啦！宝子们看懂应该没什么问题！

通过测试可以看到堆排序可以实现升序排列，并且效率更高！

4.代码

头文件：

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int HPDataType;
typedef struct Heap {
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);//插入数据并向上调整调整
void HeapPop(HP* php);//删除堆顶（根节点）

int HeapSize(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);

源文件：

#include "Heap.h"
void HeapInit(HP* php) {
	assert(php);//检查php是否为空指针
	php->a = NULL;
	php->size = php->capacity = 0;
}

void HeapDestroy(HP* php) {
	assert(php);
	free(php->a);//将a指向的动态空间还给操作系统
	php->a = NULL;//置空，避免出现野指针
	php->size = php->capacity = 0;
}
void Swap(HPDataType* p1, HPDataType* p2) {
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType* a, HPDataType child) {
	int parent = (child - 1) / 2;//找父结点
	while (child > 0) {
		if (a[child] < a[parent]) {//当子结点小于父节点时，交换
			Swap(&a[child], &a[parent]);
			child = (child - 1) / 2;
			parent = (parent - 1) / 2;
		}
		else {
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x) {
	assert(php);
	if (php->size == php->capacity) {
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;//当容量等于有效数据时，按二倍扩容
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);//动态开辟空间
		assert(tmp);//检查是否开辟成功
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);//向上调整
}

void AdjustDown(HPDataType* a, int size, int parent) {
	int child = parent * 2 + 1;
	while (child<size) {
		if (child + 1 < size && a[child + 1] < a[child]) {
			child++;
		}
		if (a[parent] > a[child]) {
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

void HeapPop(HP* php) {
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

HPDataType HeapTop(HP* php) {
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

int HeapSize(HP* php) {
	assert(php);
	return php->size;
}

bool HeapEmpty(HP* php) {
	assert(php);
	return php->size == 0;
}

测试文件：

#include "Heap.h"
int main() {
	int a[] = { 4,6,2,1,5,8,2,9 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < 8; i++) {
		HeapPush(&hp, a[i]);
	}

	while(!HeapEmpty(&hp)){
		printf("%d", HeapTop(&hp));
		HeapPop(&hp);
	}
	return 0;
}

5.结语

那今天的讨论就到这里喽！不知道大家是否有所收获呢？可以把自己的疑问发在评论区！

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

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

相关文章

线性系统理论 -- 降阶观测器的设计

线性系统理论 -- 降阶观测器的设计

定理&#xff1a; 若系统能观测&#xff0c;且rankCm&#xff0c;则系统的状态观测器的最小维数是(n-m)。 线性定常时不变系统方程如下&#xff08;以三阶(n3)单入单出系统为例&#xff0c;有mrankC1&#xff09;&#xff1a; 取变换阵P&#xff0c;有&#xff1a; 对上述系统…
阅读更多...
易宝OA系统ExecuteSqlForSingle接口SQL注入漏洞复现 [附POC]

易宝OA系统ExecuteSqlForSingle接口SQL注入漏洞复现 [附POC]

文章目录 易宝OA系统ExecuteSqlForSingle接口SQL注入漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 易宝OA系统ExecuteSqlForSingle接口SQL注入漏洞复现 [附POC] 0x01 前言 免责声明&#xff1a;请勿利用文章…
阅读更多...
前端量子纠缠 效果炸裂 multipleWindow3dScene

前端量子纠缠 效果炸裂 multipleWindow3dScene

我 | 在这里 &#x1f575;️ 读书 | 长沙 ⭐软件工程 ⭐ 本科 &#x1f3e0; 工作 | 广州 ⭐ Java 全栈开发&#xff08;软件工程师&#xff09; &#x1f383; 爱好 | 研究技术、旅游、阅读、运动、喜欢流行歌曲 ✈️已经旅游的地点 | 新疆-乌鲁木齐、新疆-吐鲁番、广东-广州…
阅读更多...
免交互语法expect

免交互语法expect

目录 前瞻 相关命令 范例一&#xff1a;免密登录另外一台主机并创建用户 范例二&#xff1a;免密登录另外三台主机并创建用户 前瞻 expect是建立在tcl&#xff08;tool command language&#xff09;语言基础上的一个工具&#xff0c;常被用于进行自动化控制和测试&#xf…
阅读更多...
HbuilderX 项目打包文件过大问题优化

HbuilderX 项目打包文件过大问题优化

文章目录 HbuilderX 项目打包文件过大问题优化主要操作收效甚微&#xff0c;但又有那么点用的方法使用 gulp 压缩&#xff08;最后一步&#xff09;使用与配置 网上找的 gulp 优化压缩配置还未尝试可能有用的方法 尝试过程中看到的一些优质文章 HbuilderX 项目打包文件过大问题…
阅读更多...
ubuntu配置免密登录vscode

ubuntu配置免密登录vscode

1、配置免密登录 &#xff08;1&#xff09;在windows系统cmd下运行命令 ssh-keygen 一路回车&#xff0c;将会在C:\Users\用户名\.ssh目录下生成两个文件&#xff1a;id_rsa和id_rsa.pub。如下图所示。 &#xff08;2&#xff09;进入.ssh目录。如果想使用root用户&#xff0…
阅读更多...
ArrayList与顺序表的简单理解

ArrayList与顺序表的简单理解

前言----list 在集合框架中&#xff0c;List是一个接口&#xff0c;继承自Collection。Collection也是一个接口&#xff0c;该接口中规范了后序容器中常用的一些方法&#xff0c;具体如下所示&#xff1a; Iterable也是一个接口&#xff0c;表示实现该接口的类是可以逐个元素进…
阅读更多...
鸿蒙4.0开发笔记之ArkTS语法基础@Entry@Component自定义组件的使用（九）

鸿蒙4.0开发笔记之ArkTS语法基础@Entry@Component自定义组件的使用（九）

文章目录 一、自定义组件概述1、什么是自定义组件2、自定义组件的优点 二、创建自定义组件1、自定义组件的结构2、自定义组件要点3、成员变量的创建4、参数传递规则 三、练习案例 一、自定义组件概述 1、什么是自定义组件 在ArkUI中&#xff0c;UI显示的内容均为组件&#xf…
阅读更多...
443. 压缩字符串

443. 压缩字符串

这篇文章会收录到 : 算法通关村第十二关-黄金挑战字符串冲刺题-CSDN博客 压缩字符串 描述 : 给你一个字符数组 chars &#xff0c;请使用下述算法压缩&#xff1a; 从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 &#xff1a; 如果这一组长度为 1 &#xff0c;…
阅读更多...
c++ opencv使用drawKeypoints、line实现特征点的连线显示

c++ opencv使用drawKeypoints、line实现特征点的连线显示

前言 图像经过算子处理后得到若干特征点&#xff0c;使用opencv进行渲染显示出这些特征点并且连线&#xff0c;更直观的对比处理前后的一些差异性 demo核心代码 //画出特征点并连线 void drawFilterLinePoints(cv::Mat& srcMat, cv::Point2f pointStart, cv::Point2f po…
阅读更多...
基于FactoryBean、实例工厂、静态工厂创建Spring中的复杂对象

基于FactoryBean、实例工厂、静态工厂创建Spring中的复杂对象

&#x1f609;&#x1f609; 学习交流群&#xff1a; ✅✅1&#xff1a;这是孙哥suns给大家的福利&#xff01; ✨✨2&#xff1a;我们免费分享Netty、Dubbo、k8s、Mybatis、Spring...应用和源码级别的视频资料 &#x1f96d;&#x1f96d;3&#xff1a;QQ群&#xff1a;583783…
阅读更多...
LD_PRELOAD劫持

LD_PRELOAD劫持

LD_PRELOAD劫持 <1> LD_PRELOAD简介 LD_PRELOAD 是linux下的一个环境变量。用于动态链接库的加载&#xff0c;在动态链接库的过程中他的优先级是最高的。类似于 .user.ini 中的 auto_prepend_file&#xff0c;那么我们就可以在自己定义的动态链接库中装入恶意函数。 也…
阅读更多...
P9240 [蓝桥杯 2023 省 B] 冶炼金属（比值问题）

P9240 [蓝桥杯 2023 省 B] 冶炼金属（比值问题）

数学分析&#xff1a; 1. max(最大比值) A/B 余数p&#xff08;p<B&#xff09; > Amax*Bp 反证&#xff1a;若max不为最大,则设maxn为最大比值 (maxn)*Bmax*Bn*Bp1 > A (n*Bp1 > p ,矛盾) 故max为最大比值 2.min(最小比值…
阅读更多...
随时随地，打开浏览器即可体验的在线PS编辑器

随时随地，打开浏览器即可体验的在线PS编辑器

即时设计 即时设计是国产的专业级 UI 设计工具&#xff0c;不限平台不限系统&#xff0c;在浏览器打开即用&#xff0c;能够具备 Photoshop 的设计功能&#xff0c;钢笔、矢量编辑、矩形工具、布尔运算等设计工具一应俱全&#xff0c;是能够在线使用的 Photoshop 免费永久工具…
阅读更多...
算法训练 第九周

算法训练 第九周

二、删除排序链表中的重复元素 II 1.遍历 由于给定的链表是排好序的&#xff0c;因此重复的元素在链表中出现的位置是连续的&#xff0c;因此我们只需要对链表进行一次遍历&#xff0c;就可以删除重复的元素。由于链表的头节点可能会被删除&#xff0c;因此我们需要额外设定一…
阅读更多...
BGP综合实验（IP）

BGP综合实验（IP）

实验要求&#xff1a; 实验思路&#xff1a; 1.划分IP地址&#xff1a; 将172.16.0.0/16的网段划分为172.16.0.0/24的多个网段&#xff0c;因为在实际工程当中&#xff0c;24的网段更符合用户网段&#xff0c;因此先将网段划分为172.16.0.0 /24的多个子网掩码为24的网段&…
阅读更多...
前五年—中国十大科技进展新闻（2012年—2017年）

前五年—中国十大科技进展新闻（2012年—2017年）

前五年—中国十大科技进展新闻&#xff08;2012-2017&#xff09; 2017年中国十大科技进展新闻1. 我国科学家利用化学物质合成完整活性染色体2. 国产水下滑翔机下潜6329米刷新世界纪录3. 世界首台超越早期经典计算机的光量子计算机诞生4. 国产大型客机C919首飞5. 我国首次海域天…
阅读更多...
Python爬虫入门：如何设置代理IP进行网络爬取

Python爬虫入门：如何设置代理IP进行网络爬取

目录 前言 一、获取代理IP 1.1 获取免费代理IP 1.2 验证代理IP 二、设置代理IP 三、使用代理IP进行网络爬取 四、总结 前言 在进行网络爬取时&#xff0c;经常会遇到一些反爬虫的措施&#xff0c;比如IP封锁、限制访问频率等。为了解决这些问题&#xff0c;我们可以使用…
阅读更多...
【LeetCode刷题】--38.外观数列

【LeetCode刷题】--38.外观数列

38.外观数列 方法&#xff1a;遍历生成 该题本质上是依次统计字符串中连续相同字符的个数 例如字符串 1112234445666我们依次统计连续相同字符的个数为: 3 个连续的字符 1, 222 个连续的 2&#xff0c;1 个连续的字符 3&#xff0c;3个连续的字符 4&#xff0c;1个连续的字符…
阅读更多...
深入理解Transformer，兼谈MHSA（多头自注意力）、LayerNorm、FFN、位置编码

深入理解Transformer，兼谈MHSA（多头自注意力）、LayerNorm、FFN、位置编码

Attention Is All You Need——集中一下注意力 Transformer其实不是完全的Self-Attention结构&#xff0c;还带有残差连接、LayerNorm、类似1维卷积的Position-wise Feed-Forward Networks&#xff08;FFN&#xff09;、MLP和Positional Encoding&#xff08;位置编码&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023