C语言植物大战数据结构二叉树堆

目录
  • 前言
  • 堆的概念
  • 创建结构体
  • 初始化结构体
  • 销毁结构体
  • 向堆中插入数据
    • 1.堆的物理结构和逻辑结构
    • 2.完全二叉树下标规律
    • 3.插入数据思路
  • 依次打印堆的值
  • 删除堆顶的值
  • 判断堆是否为空
  • 求堆中有几个元素
  • 得到堆顶的值
  • 堆排序
  • 总体代码
    • Heap.h
    • Heap.c
    • Test.c

“竹杖芒鞋轻胜马,谁怕?一蓑烟雨任平生”

C语言朱武大战数据结构专栏

C语言植物大战数据结构快速排序图文示例

C语言植物大战数据结构希尔排序算法

C语言植物大战数据结构堆排序图文示例

C语言植物大战数据结构二叉树递归

前言

此篇详细实现二叉树中的一个顺序结构的实现——堆。并实现堆排序重点是堆的规律和堆的实现

堆的概念

堆:将一些元素按完全二叉树的顺序存储方式存储在一个一维数组中。这就是堆。完全二叉树:通俗讲就是只有最后一层的节点可以满,也可以不满。但是最后一层之前的节点要满,这就叫做完全二叉树。

小堆大堆:将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。(必须满足堆的性质)

堆的性质:

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

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

注意:

1.普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。

2.现实中我们通常把堆(一种特殊的二叉树)使用顺序结构的数组来存储。

3.需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。

接下来我们用纯C实现小堆

创建结构体

因为完全二叉树更适合使用顺序结构存储。而堆就是完全二叉树,所以我们需要创建顺序表

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//a指向只一个堆数组
	size_t size;//记录堆的大小
	size_t capacity;//堆的最大容量
}HP;

初始化结构体

这一步必须要有,相当于创建变量了。

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

销毁结构体

因为是动态版的顺序表,有动态开辟就需要动态内存释放,也就是free掉a所指向的空间。

//销毁结构体
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	//free掉及时置空,防止野指针
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

向堆中插入数据

在插入数据之前,我们需要先知道堆的一个技巧。

1.堆的物理结构和逻辑结构

前面的步骤打造了一个堆的轮廓,你说它是堆吧,其实本质就是一个物理结构在内存中连续的顺序表罢了。也就是数组。如图下标从0开始。

但是要用到它的逻辑结构,需要把它想象成一个完全二叉树,就是下面图片这个样子。

好了,现在我们要向堆中插入数据了,因为顺序表尾插效率高O(1),且尾插不会大幅度改变堆的结构。所以插入数据指的是尾插。

2.完全二叉树下标规律

注意:

1.尾插注意的是size的大小,size一直指向的是即将插入的那个空间。

2.和顺序表唯一不同的是尾插后需要向上调整数据,保持小堆的从上往下依次增大的结构

3.堆中的下标是有规律的。规律公式如下

这里需要强调的是对于父亲下标的计算。父亲的下标计算公式为:parent = (child - 1) / 2;举个例子。因为假如左子树是7,右子树是8。7-1初以2是3, 但8-1初以2是3.5。但是计算机计算的结果也是3。

结论:所以管他是左子树,还是右子树,都能计算出其父亲的下标。

3.插入数据思路

最重要的思路是向上调整思想

我们以向堆中插入一个8为例。

因为size指向的是顺序表中即将插入的位置,所以直接插入就好了,但要及时让size++。

注意:尾插后size还需要指向下一个即将插入的位置。如图

然后开始向上调整8的位置。

思路:

1.让child依次和其parent比较,假如child小的话就交换两者的数据,使child的值依次向上走。然后迭代执行child = parent;parent = (child - 1) / 2;用来迭代parent和child的位置,直到child等于0。结束循环。

2.我觉得思路不难,难在把思路转换为代码然后实现。

3.注意实参传递的实参分别是数组首元素的地址,和新插入元素的下标。

//交换
void HeapSwap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
		//因为需要多次用到交换算法,所以写成一个函数,方便调用。
			HeapSwap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入堆
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//除了AdjustUp
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		//注意realloc的用法
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)* newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	++php->size;
	//唯一不同于顺序表的地方,向上调整算法
	AdjustUp(php->a, php->size - 1);
}

依次打印堆的值

插入堆后,为了可视化,我们还是打印一下看看效果。

void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

删除堆顶的值

删除也是一门艺术。今天的我是站在巨人的肩膀上学习堆的删除。

大佬们的算法思路是:

1.先让堆顶的值和堆尾的值交换O(1),然后删除O(1)交换后堆尾的值。

2.再使用向下调整O(logN)算法,先比较left和right哪个小,谁小就让parent和谁交换,然后依次迭代,使堆顶的值向下调整。直到child大于size结束循环。

因为这样的时间复杂度是相当牛的。

注意:这里有几个地方代码技巧非常绝。

1.假设左子树就是最小的值。然后比较左右子树的大小后进行调整到底谁是最小的就OK了。这是非常的绝。因为你需要关注到底是左子树小还是右子树小!

//非常绝的一个思路
if (child+1 < size &&
 a[child + 1] < a[child])
{
	++child;
}

删除代码如下。

//向下调整
AdjustDown(HPDataType* a,size_t size, size_t root)
{
	 size_t parent= root;
	 size_t child= parent * 2 + 1;
	 while (child < size)
	 {
	 //判断哪个孩子小。
		 if (child+1 < size && a[child + 1] < a[child])
		 {
			 ++child;
		 }
		 //交换父亲和孩子的值
		 if (a[child] < a[parent])
		 {
			 HeapSwap(&a[parent], &a[child]);
			 //迭代
			 parent = child;
			 child = parent * 2 + 1;
		 }
		 else
		 {
			 break;
		 }
	 }
}
//删除堆顶的值
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//交换堆顶和堆尾的值。然后删除堆尾的值
	HeapSwap(php->a, &php->a[php->size - 1]);
	--php->size;
	//向下调整
	AdjustDown(php->a, php->size, 0);
}

判断堆是否为空

当size为0时,堆即为空。

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

求堆中有几个元素

size标记的就是有几个元素。

//求堆中有几个元素
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

得到堆顶的值

需要注意的是size最少为1.当size为0时,就意味着堆已经为空。所以我们需要assert断言size不为0.

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

堆排序

堆排序即利用堆的思想来进行排序,总共分为两个步骤:

建堆

升序:建大堆

降序:建小堆(我们这里用的是建小堆)利用堆删除思想来进行排序

void HeapSort(HPDataType* a, int size)
{
	HP hp;
	HeapInit(&hp);
	//先创建一个小堆
	for (int i = 0; i < size; i++)
	{
		HeapPush(&hp, a[i]);
	}
	size_t j = 0;
	//利用堆删除思想来进行排序
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}
int main()
{
	//对a数组进行排序
	int a[] = { 4,2,7,8,5,1,0,6 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

时间复杂度分析:

时间复杂度为O(N*logN)。比冒泡排序上升了一个档次哦。

但是空间复杂度有待改进。

但是空间复杂度因为占用了一个数组所以是O(N)。

空间复杂度改进的话需要很多字来详解。下篇博文继续叙述。

总体代码

Heap.h

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
//初始化结构体
void HeapInit(HP* php);
//销毁结构体
void HeapDestroy(HP* php);
//向堆里插入数据
void HeapPush(HP* php, HPDataType x);
//交换堆中父子
void HeapSwap(HPDataType* pa, HPDataType* pb);
//删除堆顶数据
void HeapPop(HP* php);
//按照下标打印堆
void HeapPrint(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//求堆中有几个元素
size_t HeapSize(HP* php);
//得到堆顶的值
HPDataType HeapTop(HP* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
//初始化结构体
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
//销毁结构体
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
//交换
void HeapSwap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			HeapSwap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 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);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	++php->size;
	//向上调整
	AdjustUp(php->a, php->size - 1);
}
//向下调整
AdjustDown(HPDataType* a,size_t size, size_t root)
{
	 size_t parent= root;
	 size_t child= parent * 2 + 1;
	 while (child < size)
	 {
		 if (child+1 < size && a[child + 1] < a[child])
		 {
			 ++child;
		 }
		 if (a[child] < a[parent])
		 {
			 HeapSwap(&a[parent], &a[child]);
			 parent = child;
			 child = parent * 2 + 1;
		 }
		 else
		 {
			 break;
		 }
	 }
}
//删除堆的值
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//交换堆顶和堆尾的值。然后删除堆尾的值
	HeapSwap(php->a, &php->a[php->size - 1]);
	--php->size;
	//向下调整
	AdjustDown(php->a, php->size, 0);
}
//打印堆
void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
//求堆中有几个元素
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
//得到堆顶的值
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

Test.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void testHeap()
{
	HP hp;
	HeapInit(&hp);
	HeapPush(&hp, 5);
	HeapPush(&hp, 4);
	HeapPush(&hp, 3);
	HeapPush(&hp, 2);
	HeapPush(&hp, 1);
	HeapPrint(&hp);
	/*HeapPop(&hp);
	HeapPrint(&hp);*/
	HeapDestroy(&hp);
}
void HeapSort(HPDataType* a, int size)
{
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < size; i++)
	{
		HeapPush(&hp, a[i]);
	}
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}
int main()
{
	/*testHeap();*/
	int a[] = { 4,2,7,8,5,1,0,6 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

以上就是C语言植物大战数据结构二叉树堆的详细内容,更多关于C语言二叉树堆的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言二叉树的三种遍历方式的实现及原理

    二叉树遍历分为三种:前序.中序.后序,其中序遍历最为重要.为啥叫这个名字?是根据根节点的顺序命名的. 比如上图正常的一个满节点,A:根节点.B:左节点.C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右):中序顺序是BAC(先左后根最后右):后序顺序是BCA(先左后右最后根). 比如上图二叉树遍历结果 前序遍历:ABCDEFGHK 中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA 分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析) 下面介绍一下,二

  • C语言实现二叉树的基本操作

    二叉树是一种非常重要的数据结构.本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历.中序遍历.后序遍历.层次遍历),二叉搜索树的构造等. 1. 二叉树的构建 二叉树的基本构建方式为:添加一个节点,如果这是一棵空树,则将该节点作为根节点:否则按照从左到右.先左子树后右子树的顺序逐个添加节点.比如依次添加节点:1,6,10,2,7,11,则得到的二叉树为: 在这里,我们需要借助一个链表来保存节点,以实现二叉树的顺序插入,具体做法如下: 1.0 初始化一个用来保存二叉树节

  • C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

  • C语言数据结构二叉树之堆的实现和堆排序详解

    目录 一.本章重点 二.堆 2.1堆的介绍 2.2堆的接口实现 三.堆排序 一.本章重点 堆的介绍 堆的接口实现 堆排序 二.堆 2.1堆的介绍 一般来说,堆在物理结构上是连续的数组结构,在逻辑结构上是一颗完全二叉树. 但要满足 每个父亲节点的值都得大于孩子节点的值,这样的堆称为大堆. 每个父亲节点的值都得小于孩子节点的值,这样的堆称为小堆. 那么以下就是一个小堆. 百度百科: 堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆. 若将和此次序列对应的一维数

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • C语言植物大战数据结构二叉树堆

    目录 前言 堆的概念 创建结构体 初始化结构体 销毁结构体 向堆中插入数据 1.堆的物理结构和逻辑结构 2.完全二叉树下标规律 3.插入数据思路 依次打印堆的值 删除堆顶的值 判断堆是否为空 求堆中有几个元素 得到堆顶的值 堆排序 总体代码 Heap.h Heap.c Test.c “竹杖芒鞋轻胜马,谁怕?一蓑烟雨任平生” C语言朱武大战数据结构专栏 C语言植物大战数据结构快速排序图文示例 C语言植物大战数据结构希尔排序算法 C语言植物大战数据结构堆排序图文示例 C语言植物大战数据结构二叉树递归

  • C语言植物大战数据结构二叉树递归

    目录 前言 一.二叉树的遍历算法 1.构造二叉树 2.前序遍历(递归图是重点.) 3.中序遍历 4.后序遍历 二.二叉树遍历算法的应用 1.求节点个数 3.求第k层节点个数 4.查找值为x的节点 5.二叉树销毁 6.前序遍历构建二叉树 7.判断二叉树是否是完全二叉树 8.求二叉树的深度 三.二叉树LeetCode题目 1.单值二叉树 2. 检查两颗树是否相同 3. 对称二叉树 4.另一颗树的子树 6.反转二叉树 " 梧桐更兼细雨,到黄昏.点点滴滴." C语言朱武大战数据结构专栏 C语言

  • C语言植物大战数据结构快速排序图文示例

    目录 快速排序 一.经典1962年Hoare法 1.单趟排序 2.递归左半区间和右半区间 3.代码实现 二.填坑法(了解) 1.单趟思路 2.代码实现 三.双指针法(最佳方法) 1.单趟排序 2.具体思路 3.代码递归图 4.代码实现 四.三数取中优化(最终方案) 1.三数取中 2.代码实现(最终代码) 五.时间复杂度(重点) 1.最好情况下 2.最坏情况下 3.空间复杂度 六.非递归写法 1.栈模拟递归快排 2.队列实现快排 浅浅总结下 “田家少闲月,五月人倍忙”“夜来南风起,小麦覆陇黄” C

  • C语言植物大战数据结构希尔排序算法

    目录 前言 一.插入排序 1.排序思路 2.单趟排序 详细图解 3.整体代码 4.时间复杂度 (1).最坏情况下 (2).最好情况下 (3).基本有序情况下(重点) 5.算法特点 二.希尔排序 1.希尔从哪个方面优化的插入排序? 2.排序思路 3.预排序 4.正式排序 5.整体代码 6.时间复杂度 (1).while循环的复杂度 (2).每组gap的时间复杂度 结论: “至若春和景明,波澜不惊,上下天光,一碧万顷,沙鸥翔集,锦鳞游泳,岸芷汀兰,郁郁青青.” C语言朱武大战数据结构专栏 C语言植物

  • C语言植物大战数据结构堆排序图文示例

    目录 TOP.堆排序前言 一.向下调整堆排序 1.向下调整建堆 建堆的技巧 建堆思路代码 2.向下调整排序 调整思路 排序整体代码 3.时间复杂度(难点) 向下建堆O(N) 向下调整(N*LogN) 二.向上调整堆排序 1.向上调整建堆 2.建堆代码 “大弦嘈嘈如急雨,小弦切切如私语”“嘈嘈切切错杂弹,大珠小珠落玉盘” TOP.堆排序前言 什么是堆排序?假如给你下面的代码让你完善堆排序,你会怎么写?你会怎么排? void HeapSort(int* a, int n) { } int main(

  • C语言 深入解读数据结构之堆的实现

    堆的概念与结构 概念:如果有一个关键码的集合K={ k0,k1 ,k2 ,-,kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足K i<=K 2*i+1且Ki<=K 2*i+2(K i>=K 2*i+1且Ki>=K 2*i+2) i = 0,1,2...,则称为小堆(或大堆).将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆. 性质: 堆中某个节点的值总是不大于或不小于其父节点的值: 堆总是一棵完全二叉树. 结构: 1.大堆 2

  • C语言数据结构之堆、堆排序的分析及实现

    目录 1.堆的概念结构及分类 1.2堆的分类 1.2.1 大堆 1.2.2 小堆 2. 堆的主要接口 3.堆的实现 3.1 堆的初始化 HeapInit 3.2 堆的销毁 HeapDestory 3.3 堆的打印 HeapPrint 3.4 堆的插入元素 HeapPush   * 3.5 堆的删除元素 HeapPop  * 4.堆的应用:堆排序   *** 4.1 堆排序实现过程分析 4.3 堆排序结果演示 5.堆(小堆)的完整代码 总结  1.堆的概念结构及分类 以上这段概念描述看起来十分复杂

  • C语言数据结构二叉树简单应用

     C语言数据结构二叉树简单应用 在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree),接下来我就在这里给大家介绍一下二叉树在算法中的简单使用: 我们要完成总共有 (1)二叉树的创建 (2)二叉树的先中后序递归遍历 (3)统计叶子结点的总数 (4)求树的高度 (5)反转二叉树 (6)输出每个叶子结点到根节点的路径 (7)输出根结点到每个叶子结点的路径. 定义二叉树结点类型

随机推荐