数据结构——二叉树之c语言实现堆与堆排序

目录

前言:

1.二叉树的概念及结构

1.1 特殊的二叉树 

1.2 二叉树的存储结构

   1.顺序存储

2.链式存储 

2. 二叉树的顺序结构及实现 

2.1 堆的概念 

  ​编辑

2.2 堆的创建

3.堆的实现

3.1 堆的初始化和销毁 

初始化:

销毁: 

插入:

向上调整:

删除: 

向下调整: 

堆顶元素: 

判空: 

 4.堆排序

4.1排序实现

 


前言:

   在上一期我们介绍了有关于树的基础概念,了解了关于树的各名称的含义,然而在现实中树被用得最多的场景还是在我们计算机中的资源管理器的文件存储结构中,在其他场景被使用的情况很少,所以我们这一期要介绍一种被广泛使用的树型结构——二叉树。

1.二叉树的概念及结构

  顾名思义,二叉树是由一个根结点和两棵子树构成,二叉树的每个结点最多只有两个结点:

从上图可以看出:

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树  

二叉树是由以下几种情况复合而成的:

 

现实中的二叉树:

1.1 特殊的二叉树 

 1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数K次方-1,则它就是满二叉树。

2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

1.2 二叉树的存储结构

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

   1.顺序存储

  顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺 序存储在物理上是一个数组,在逻辑上是一颗二叉树。 

2.链式存储 

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

 

2. 二叉树的顺序结构及实现 

  普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段

2.1 堆的概念 

  

堆的性质:

1.堆中某个结点的值总是不大于或不小于其父结点的值。

2.堆总是一棵完全二叉树。 

 

2.2 堆的创建

  下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算 法,把它构建成一个堆。根结点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子结点的子树开始调整,一直调整到根结点的树,就可以调整成堆。

3.堆的实现

 介绍完堆的概念和性质之后,我们接下来就要来用代码实现堆及堆的各个方法。由于堆是顺序结构实现的,所以我们选择使用顺序表来实现它:

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

3.1 堆的初始化和销毁 

  堆是用顺序表来实现的,而顺序表的空间都是我们手动在内存中的堆中开辟的,所以也需要手动释放,而在程序最初运行时我们也要对它进行初始化。

初始化:

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}//初始化

销毁: 

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}//销毁

插入:

 在插入数据之前,我们选确定空间够不够,如果city等于cpapcity,我们就判断空间满了,需要扩容,然后插入数据,而要实现建堆的话,我们还需要使用向上调整方法实现:

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
		}
		php->a = tmp;
		php->capacity = newcapacity;

	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size-1);//向上调整
}//插入

向上调整:

   向上调整是建堆的关键,在我们插入一个数据时,我们之前建的堆可能会遭到破坏,这时就需要重新调整建堆,我们插入操作是尾插,用堆来表示的话它就是在堆低,这时我们就要向上调整,如果我们建的是小堆,那么我们就要判断我们插入的结点与它的父结点的大小关系,如果它比它的父结点小的话。那么就要与它的父结点交换位置,走到下一轮,如果它还是小于自己的父节点,那么继续执行交换操作,直到数组变成一个小堆:

代码实现:

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;
		}
	}
}

删除: 

  有插入操作就必然有删除操作,那么我们如何实现删除操作呢?如果我们直接进行头删,那么我们建的堆就会被破环,如果尾删的话,那么堆就没有意义了(后面详细解释),所以我们先让堆中第一个元素与最后一个元素交换,然后再让size减一,而这时我们建的堆被破环了,所以还需要使用向下调整方法来重新建堆,而向下建堆的算法也比较简单,先找出第一个结点更小的那个子结点,只要这个结点比它的父结点小就让它们交换位置,如此循环往复,直到走到堆尾:

删除代码实现:

void HPPop(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);//向下调整
}//删除

向下调整: 

void AdjustDown(HPDataType* a, int n, int parent)
{
	//假设更小的孩子是左孩子
	int child = parent * 2 + 1;
	while (child<n)//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;
		}
	}
	
}//向下调整

堆顶元素: 

HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}//堆顶元素

判空: 

bool HPEmpty(HP* php)
{
	assert(php);
	return php->size = 0;
}//判空

 4.堆排序

 堆排序是一种速度很快的排序算法,冒泡排序的时间复杂度为O(N^2),而堆排序的时间复杂度仅为O(logN),学完堆,我们就可以来试着实现堆排序了。

4.1排序实现

 我们先创建一个无序数组:

int a[] = { 8,6,5,3,9,0,7,1,4,2 };

现在这个数组不是堆,我们堆排序的第一步就是先建堆呢,可以使用向下调整吗,答案是不可以,只有下面的子树都是堆时才可以使用,而现在这棵树仅是一个无序数组,所以我们选择从后往前建堆,什么意思呢,我们可以把这组树看成一棵一棵树:

 

我们发现,从9开始,往上每一个结点都有自己的子结点,这就意味着从就开始,每往前走一步就是一棵树,所以我们只要从9开始使用向下调整建堆,每往前走一步就可以实现一棵树的建堆,而走到8时,整棵树也就完成了建堆:

int a[] = { 8,6,5,3,9,0,7,1,4,2 };
int len = sizeof(a) / sizeof(int);
for (int i = (len - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(a, len, i);
}//建堆

这个算法到底怎么样呢?我们运行一下程序看看:

 

我们将这些数字摆成一棵二叉树:

 

从上图可以看出,这组数字摆成一棵二叉树它就是一个标准的堆。 

     成功建堆之后,我们就可以来使用堆来排序了,从上图可以看出,我们建的是小堆,如果我们要实现降序,可以使用小堆实现吗?答案是可以,而且经过实验,我们得出结论:升序:建大堆降序:建小堆,所以我们使用小堆来实现降序是没有问题的。如何实现呢,我们可以先创建一个变量end指向最后一个结点,然后让第一个结点和尾结点交换,因为第一个结点是整个堆最小的数,交换位置之后,最小的数就在最后一个结点了,我们让end向前走一步,然后使用向下调整让堆第二小的数字走到第一个结点,然后再和end指向的结点交换,循环往复之后最大的数就走到了第一个结点,而我们也完成了降序排序:

while (end > 0)
    {
        swap(&a[0], &a[end]);
        end--;
        AdjustDown(a, end, 0);
        
    }//调整

来看看结果:

 

 下面是完整代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
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 test()
{
	int a[] = { 8,6,5,3,9,0,7,1,4,2 };
	int len = sizeof(a) / sizeof(int);
	for (int i = (len - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, len, i);
	}//建堆

	

	int end = len - 1;

	while (end > 0)
	{
		swap(&a[0], &a[end]);
		end--;
		AdjustDown(a, end, 0);
		
	}//调整
	
	for (int i = 0; i < len; i++)
	{
		printf("%d ", a[i]);
	}
}
int main()
{
	test();
	return 0;
}

到这里我们的堆就结束了,我将代码放在下面,感兴趣的小伙伴可以试试哦。

Heap.h :

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

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

void HPInit(HP* php);//初始化
void HPDestroy(HP* php);//销毁
void HPPush(HP* php, HPDataType x);//插入
void HPPop(HP* php);//删除
HPDataType HPTop(HP* php);//堆顶元素
void AdjustUp(HPDataType* a, int child);//向上调整
void AdjustDown(HPDataType* a, int n,int parent);//向下调整
bool HPEmpty(HP* php);//判空

Heap.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}//初始化
void swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}//交换
void AdjustDown(HPDataType* a, int n, int parent)
{
	//假设更小的孩子是左孩子
	int child = parent * 2 + 1;
	while (child<n)//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 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 HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
		}
		php->a = tmp;
		php->capacity = newcapacity;

	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size-1);//向上调整
}//插入
void HPPop(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 HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}//堆顶元素
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size = 0;
}//判空

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}//销毁

test.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void test()
{
	int a[] = { 4,9,0,2,5,3,7,1,8,6 };
	HP hp;
	HPInit(&hp);
	for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}
	while (hp.size)
	{
		printf("%d ", hp.a[hp.size - 1]);
		hp.size--;
	}
	HPDestroy(&hp);
}
void test02()
{
	int a[] = { 4,9,0,2,5,3,7,1,8,6 };
	HP hp;
	HPInit(&hp);
	for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}

	while (hp.size>0)
	{
		int top = HPTop(&hp);
		printf("%d ", top);
		HPPop(&hp);
	}

	HPDestroy(&hp);

}
void test03()
{
	int a[] = { 4,9,0,2,5,3,7,1,8,6 };

	size_t len = sizeof(a) / sizeof(int);
	for (int i = (len - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, len, i);
	}
	int end = len - 1;

	while (end>0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}

	for (int i = 0; i < len; i++)
	{
		printf("%d ", a[i]);
	}
}
int main()
{
	//test02();
	test03();
	return 0;
}

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

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

相关文章

C-10 凸包

凸包 数学定义 平面的一个子集S被称为是凸的&#xff0c;当且仅当对于任意两点A&#xff0c;B属于S&#xff0c;线段PS都完全属于S过于基础就不详细介绍了 凸包的计算 github上找到了别人的代码&#xff0c;用4种方式实现了凸包的计算&#xff0c;把他放在这里链接地址htt…

LibreOffice的国内镜像安装地址和node.js国内快速下载网站

文章目录 1、LibreOffice1.1、LibreOffice在application-conf.yml中的配置2、node.js 1、LibreOffice 国内镜像包网址&#xff1a;https://mirrors.cloud.tencent.com/libreoffice/libreoffice/ 1.1、LibreOffice在application-conf.yml中的配置 jodconverter:local:enable…

平安消保在行动 | 守护每一个舒心笑容 不负每一场双向奔赴

“要时刻记得以消费者为中心&#xff0c;把他们当做自己的朋友&#xff0c;站在他们的角度去思考才能更好地解决问题。” 谈及如何成为一名合格的消费者权益维护工作人员&#xff0c;平安养老险深圳分公司负责咨诉工作的庞宏霄认为&#xff0c;除了要具备扎实的专业技能和沟通…

安全及应用(更新)

一、账号安全 1.1系统帐号清理 #查看/sbin/nologin结尾的文件并统计 [rootrootlocalhost ~]# grep /sbin/nologin$ /etc/passwd |wc -l 40#查看apache登录的shell [rootrootlocalhost ~]# grep apache /etc/passwd apache:x:48:48:Apache:/usr/share/httpd:/sbin/nologin#改变…

const 修饰不同内容区分

1.修饰局部变量 const int a 1;int const a 1; 这两种是一样的 注意&#xff1a; const int b; 该情况下编译器会报错&#xff1a;常量变量"b”需要初始值设定项 将一个变量没有赋初始值直接const修饰后&#xff0c;在以后时无法更改内容的。 2.修饰常量字符串 a.…

算法题:用JS实现删除链表的倒数第N个节点

学习目标&#xff1a; 删除链表的倒数第N个节点 leetcode原题链接 学习内容&#xff1a; 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点 示例 1: 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5] 示例 2: 输入&a…

基于YOLOv9的线路绝缘子缺陷检测【python源码+UI界面+数据集+模型+语音报警+安装说明】

往期精品导航 基于YOLOv9的脑肿瘤区域检测智慧课堂基于YOLOv8的学生上课行为检测基于YOLOv9pyside的安检仪x光危险物物品检测&#xff08;有ui&#xff09;基于YOLOv9的PCB板缺陷检测 前言 高压输电线绝缘子是电力输送系统中关键的组成部分&#xff0c;负责防止电流泄露&…

Trinity:转录组从头组装

安装 #下载安装包 wget -c https://github.com/trinityrnaseq/trinityrnaseq/releases/download/Trinity-v2.15.1/trinityrnaseq-v2.15.1.FULL.tar.gztar -xzvf trinityrnaseq-v2.15.1.FULL.tar.gz cd trinityrnaseq-v2.15.1 make make plugins #安装依赖 mamba install -c bio…

收银系统源码-次卡功能

智慧新零售收银系统是一套线下线上一体化收银系统&#xff0c;给门店提供了含线下收银称重、线上商城、精细化会员管理、ERP进销存、营销活动、移动店务助手等一体化行业解决方案&#xff01; 详细功能见下文&#xff1a; 门店收银系统源码-CSDN博客文章浏览阅读2.6k次&#…

SDK环境的安装(测试使用)

1、安装 将文件解压至目录,我的目录为:D:\Program Files\Android 解压后如下: 下载链接如下: sdk下载 提取码见文章最后: 2、配置环境 1、在环境变量中,选择系统变量,点击新建。 变量名:ANDROID_HOME 变量值:“你自己的android-sdk安装路径” (例如我的:D:\Pro…

大语言模型的应用探索AI Agent初探!

前言 大语言模型的应用之一是与大语言模型进行聊天也就是一个ChatBot&#xff0c;这个应用已经很广泛了。 接下来的一个应用就是AI Agent。 AI Agent是人工智能代理&#xff08;Artificial Intelligence Agent&#xff09;的概念&#xff0c;它是一种能够感知环境、进行决策…

算法训练营day26--455.分发饼干+376. 摆动序列+53. 最大子序和

一、455.分发饼干 题目链接&#xff1a;https://leetcode.cn/problems/assign-cookies/ 文章讲解&#xff1a;https://www.programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html 视频讲解&#xff1a;https://www.bilibili.com/video/BV1MM411b7cq 1.1 初见思…

如何优化 PostgreSQL 中对于自关联表的查询?

文章目录 一、理解自关联表查询二、分析性能问题的可能原因&#xff08;一&#xff09;缺少合适的索引&#xff08;二&#xff09;大量数据的笛卡尔积&#xff08;三&#xff09;复杂的查询逻辑 三、优化策略及解决方案&#xff08;一&#xff09;创建合适的索引&#xff08;二…

史上最经典大型主机

注&#xff1a;本文资料有点老&#xff0c;但用来快速了解 IBM 大型机演进还不错。 1、大型机不为人知的秘密 自从发明计算机以来&#xff0c;人类的信息化历史进程得以加速推进。如果将全球各地的 PC 比大树上的枝繁叶茂&#xff0c;点缀一方沃土摇曳一股清风&#xff1b;那…

Servlet与Servlet容器

什么是Servlet? Servlet是Java EE&#xff08;现称Jakarta EE&#xff09;中的一个组件&#xff0c;通常用于创建动态Web内容。Servlet是运行在Web服务器上的Java程序&#xff0c;它处理客户端的请求并生成响应。Servlet的核心功能是处理HTTP请求和响应。下面是一个servlet例…

AIGC时代程序员的跃迁——编程高手的密码武器

大家好&#xff0c;我是herosunly。985院校硕士毕业&#xff0c;现担任算法研究员一职&#xff0c;热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名&#xff0c;CCF比赛第二名&#xff0c;科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的…

《初级C++》(一)

初级C&#xff08;一&#xff09; 1: C参考⽂档2&#xff1a;C创建与实现创建C的第一套程序命名空间的理解空间命名的实现C输⼊&输出缺省参数 1: C参考⽂档 https://legacy.cplusplus.com/reference/ 《非官方》 https://zh.cppreference.com/w/cpp 《官方中文版》 https:/…

学java的第3天 后端商城小程序工作

1.数据库的大坑 特殊字段名 ’我的图片表中有一个字段是描述我写成desc了&#xff0c;正好是mysql中的关键字 就不能使用了 2.后端编写 2.1可以把请求分开 在商品浏览页中 只显示商品的大致信息 当用户再点击其他按钮时在发出请求 2.2把请求合并 把数据整合到一起 利用ass…

Git秘籍大公开:从基础概念到高级技巧的全面解析

文章目录 前言一、Git基础介绍1. 作用2. 为什么要进行源代码管理?3. Git的诞生4. Git管理源代码特点5. Git操作流程图解 二、工作区暂存区和仓库区介绍1. 工作区2. 暂存区3. 仓库区 三、Git单人本地仓库操作1. 安装git2. 查看git安装结果3. 创建项目4. 创建本地仓库5. 配置个人…

前端JS特效第24集:jquery css3实现瀑布流照片墙特效

jquery css3实现瀑布流照片墙特效&#xff0c;先来看看效果&#xff1a; 部分核心的代码如下(全部代码在文章末尾)&#xff1a; <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8" /> <title>jquerycss3实现瀑…