• 【数据结构】树的概念与堆的实现

    树的概念与堆的实现

    1、什么是树

    1.1 树的概念

    树是一种非线性的数据结构，它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像是一颗倒挂的树，也就是说它是根朝上，而叶朝下的。

    • 有一个特殊的结点，称为根节点，根节点没有前驱节点
    • 除根节点外，其余节点被分成M（M>0）个互不相交的集合T1、T2……、Tm，其中每一个集合Ti（1<=i<=m）又是一颗结构与树类似的子树。每一颗子树的根节点有且只有一个前驱，可以有0个或多个后继
    • 因此树是递归定义的。
      在这里插入图片描述
      注意：树型结构中，子树之间不能有交集，否则就不是树型结构，如下
      在这里插入图片描述

    1.2 树的相关概念

    在这里插入图片描述

    • 节点的度：一个节点含有的子树的个数称为该节点的度：如上图：A的为6
    • 叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I…等节点为叶节点
    • 非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G…等节点为分支节点
    • 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父亲节点
    • 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点：如上图：B是A的孩子节点
    • 兄弟节点：具有相同父节点的节点互称为兄弟节点：如上图：B、C是兄弟节点
    • 树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6
    • 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，依次类推
    • 树的高度或深度：树中节点的最大层次；如上图：树的高度为4
    • 堂兄弟节点：双亲在同一层的节点互为堂兄节点；如上图：H、I互为堂兄弟节点
    • 节点的祖先：从根节点到该节点所经分支节点上的所有节点 ；如上图：A是所有节点的祖先
    • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
    • 森林：由m（m>0）颗互不相交的树的集合称为森林。

    1.3 树的表示

    树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保持值域，也要保存节点和节点的关系，实际中树有很多种表示方式如：双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。这里着重介绍最常用的孩子兄弟表示法（左孩子右兄弟）。

    typedef int DataType;
struct Node
{
	struct Node* child;    //第一个孩子节点
	struct Node* brother;  //指向其下一个兄弟节点
	DataType data;         //其中的数据域
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    在这里插入图片描述

    2、二叉树概念及结构

    2.1 概念

    一颗二叉树是节点的一个有限集合，该集合：
    1.或者为空
    2.或者由一个节点加上两颗分别被称为左子树和右子树的二叉树组成

    在这里插入图片描述
    从上图可以看出：
    1.二叉树不存在度大于2的节点
    2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

    注意：对于任意的二叉树都是由以下几种情况复合而成的：
    在这里插入图片描述

    2.2 特殊的二叉树

    1. 满二叉树：一个二叉树，如果每一个层的节点树都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且节点总数是2^k-1(等比数列求和)，则它就是满二叉树。
    2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而印出来的。对于深度为K的，有n节点的二叉树，当且仅当其每一个节点都与深度为K的满二叉树中编号从1至n的节点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊完全二叉树。
      在这里插入图片描述

    2.3 二叉树的性质

    1.若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^（i-1）个节点。
    2.若规定根节点的层数为1，则深度为h的二叉树的最大根节点树是(2^h)-1。
    3.对任何一颗二叉树，如果度为0其节点个数为n0，度为2的分支节点个数为n2，则有n0=n2+1。
    4.若规定根节点的层数为1，具有n个根节点的满二叉树的深度，h=log2（n+1）（log以2为底，n+1为对数）
    5.对于具有n个节点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的节点有：

    1、若i>0，i位置节点的双亲序号：（i-1）/2；i=0，i为根节点编号，无双亲节点
    2、2i+1=n否则无左孩子
    3、2i+1=n否则无右孩子

    2.4 二叉树的存储结构

    二叉树一般可以使用两种结构存储，一种顺序存储，一种链式存储
    1、顺序存储
    顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上一颗二叉树。
    在这里插入图片描述
    2、链式存储
    二叉树的链式存储结构是指，用链来表示一颗二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来给出该节点左孩子和右孩子所在的链式节点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。

    在这里插入图片描述

    3、二叉树的顺序结构及实现

    3.1 二叉树的顺序结构

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

    3.2 堆的概念及结构

    如果有一个关键码的集合K={k0，k1，k2，…，k（n-1）}，把它的所有元素按完全二叉树的顺序存储方式在一个一维数组中，并满足：Ki<=K2i+1且Ki<=K2i+2（Ki>=K2i+1且Ki>=K2i+2）i=0，1，2…，则称为小堆（或大堆）。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

    堆的性质：

    • 堆中某个节点的值总是不大于或不小于其父亲节点的值；
    • 堆总是一颗完全二叉树。
      在这里插入图片描述

    3.3 堆的实现

    3.3.1 创建一个堆

    在.c文件中用一个结构体创建一个堆

    //创建一个小根堆，小根堆的具体实现在插入函数中引用的向上调整函数，以此不断插入就能创建堆
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;   //堆用数组实现，创建一个整形数组用来存放堆的数据
	int size;        //堆当前的实际大小
	int capacity;    //堆的容量
}HP;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    1. 结构体中包含了实现堆的数组a、堆的当前的实际大小与堆的容量。
    2. 因为堆可以插入与删除，所以堆的大小要求是可变的，即要求实现堆的数组是动态开辟的，动态开辟的空间用一个指针存储其首地址。

    3.3.2 初始化堆

    void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    1. 在堆中还没有任何数据时，数组中也没有任何数据，即还没有动态开辟空间，将指针指向一个空指针。
    2. 此时，堆的当前大小与总容量都是0。

    3.3.3 堆的插入函数以及向上调整函数

    插入x以后依然保持堆的形状

    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, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("ralloc fail");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	//扩容完后将数据插入到堆的最后一个位置（数组的最后一个位置）
	php->a[php->size] = x;
	php->size++;

	//将插入的数据根据情况向上调整
	AdjustUp(php->a, php->size - 1);  //将数组和数组中最后一个数的下标传过去
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    1. 先对接受的形参判空
    2. 插入之前先检查堆中是否还有多余的空间以供插入。当前大小与总容量相等时，说明堆已经满了，需要动态开辟空间。
    3. 堆满了有两种情况，一种是堆刚刚初始化，还没有往里面储存任何内容，这时可以先给他四个整形大小的空间（动态开辟四个整形空间的大小）（也可以多给点，看自己）；另一种是，已经储存了数据，当时数组已经没有多余的空间，这时动态开辟原有空间两倍大小的空间（为什么是两倍，因为如果开多了，空间会浪费，如果开小了，需要频繁动态开辟空间，造成空间碎片化）。
    4. 将动态开辟空间的首地址指向数组a
    5. 空间足够以后，将需要插入的数据插入到数组的最后一个位置上，即堆的最后子节点，这样不会破坏堆整体的父子关系。
    6. 创建一个向上调整函数，将插入的子节点与其父节点进行比较，根据是大根堆还是小根堆，将子节点与父节点位置关系进行调整，以维持堆的形状。

    向上调整函数

    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)   //孩子的下标等于0时，说明堆从最后一个数一路向上比较，已经到达堆顶了
	{
		//小根堆，任意孩子的值要大于父节点的值，不是的话则要向上调整
		if (a[child] < a[parent])   //改为>，这个堆结构就成为大堆了
		{
			Swap(&a[child], &a[parent]);

			//修正父亲与孩子的下标，通过循环不断比较，直到成为堆的形状
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    在这里插入图片描述
    在这里插入图片描述

    1. 向上调整函数将整个数组与数组最后一个下标传过去，即向上调整函数是将堆中最后的元素与其父节点进行比较，依次向上调整。
    2. 当插入一个节点后，找到其父节点，子节点与父节点的坐标关系如下：

    leftchild = parent * 2 + 1，左孩子的数组下标都是奇数
    rightchild = parent * 2 + 2，右孩子的数组下标都是偶数
    parent = (child - 1)/2，对于由子节点找父节点，不论是左孩子还是右孩子，都是这个公式，因为对于同一父节点的奇数子节点与偶数子节点-1除2得到的结果都是一样的。

    1. 对于小根堆来说，父节点小于等于子节点，如果插入的子节点小于其父节点，将子节点与其父节点进行交换，交换完毕后，修正子节点与父节点的下标，通过循环，不断往堆顶修正，直到循环终止。
    2. 循环终止条件，当子节点等于0了，说明已经向上调整到堆顶了。或者不满足修正条件，直接break出来。

    在主函数中调用插入函数

    int main()
{
	//int a[] = { 15,18,19,25,28,34,65,49,27,37 };
	int a[] = { 65,100,70,32,50,60 };
	HP hp;
	HeapInit(&hp);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);    //依次插入，插入完成后就是堆的形状
	}

	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    调试结果

    在这里插入图片描述

    在这里插入图片描述

    1. 创建一个堆 HP hp;，将堆 hp初始化HeapInit(&hp);
    2. 给定一组数{ 65,100,70,32,50,60 }，根据插入函数依次插入，最终得到堆的形状{ 32,50,60,100,65,70 }
    3. 这个插入函数随着树的插入，堆也随之构建完成。

    3.3.4 堆的打印

    //判空函数
bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    1. 堆的打印就是依次将数组中的元素遍历一遍，访问一个数打印一个数，知道数组访问完毕。
    2. 堆的打印首先堆传过来的指针进行断言，防止传过来的是空指针。
    3. 再对传过来的堆进行判空，如果堆中没有储存元素，也就不用再进行接下来的打印了。

    3.3.5 删除堆顶元素以及向下调整函数

    //向下调整函数
void AdjustDown(HPDataType* a, int n, int parent)
{
	int minChild = parent * 2 + 1; //先默认左边的孩子是整个小根堆中次小的孩子
	while (minChild < n)
	{
		//与右孩子比较一下，找出小的那个孩子的下标
		if (minChild + 1 < n && a[minChild + 1] < a[minChild])
		{
			minChild++;
		}
		//找到次小的孩子后将其与父节点比较
		if (a[minChild] < a[parent])
		{
			Swap(&a[minChild], &a[parent]);
		    //修正父亲与孩子的下标，通过循环不断比较，直到成为堆的形状
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
	
}

//删除堆顶的元素 --找次大或者次小，小堆找次小，大堆找次大
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	//将堆顶元素与堆中最后一个元素交换，然后将最后一个元素删除，这样堆顶元素就被删除了。
	Swap(&(php->a[0]), &(php->a[php->size - 1]));
	php->size--;

	//向下调整，对于小根堆来说，找到次小元素，将其作为堆的堆顶，然后向下不断调整，恢复之前小根堆的形状。
	AdjustDown(php->a, php->size, 0);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    1. 删除堆顶元素后，要保证堆依然要保持堆的形状，所以不能将数组中的第一个元素删除掉，然后将数组的第二个元素提到前面来作为根节点，这样会将原本的兄弟关系变成父子关系，打乱堆的形状。将打乱的堆重新插入一遍回复堆的形状非常的浪费时间。
    2. 删除堆顶元素最好的方式是将堆顶元素与最后一个元素进行交换，交换后，将最后一个元素删除，这时堆顶元素就被删除了。堆顶元素被删除后，其他层级的父子关系并没有被打乱，只有新调换上来的堆顶元素不符合堆，这时创建一个现下调整函数，对于小根堆来说，找到原来堆中的次小元素，由其来作为堆顶元素（对于大根堆来说，找到原来堆中的次大元素，由其来作为堆顶元素）。
    3. AdjustDown(php->a, php->size, 0); 向下调整函数，将数组和数组的大小，以及堆顶元素的坐标传过去。
    4. 向下调整函数一个重要的功能就是找到次小或次大的节点，然后将其作为根节点。这段代码是小根堆，所以向下找次小的孩子。
    5. 先默认为左孩子是整个小根堆中次小的节点，将左孩子与右孩子比较一下，如果右孩子比左孩子小，就将其值赋给次小孩子。找到次小孩子后，将其与父节点进行比较，将次小孩子换到根节点上位置去。然后将父节点与子节点的坐标进行修正，通过循环，不断将父节点与子节点进行交换，直到循环终止。
    6. 循环终止条件，当子节点的坐标等于堆中的当前实际大小时，说明已经循环已经来到最后，所有的都已经进行比较过了。循环终止的另一条件是，当子节点与父节点不用交换，直接break出来。

    在主函数中调用删除堆顶元素函数

    int main()
{
	//int a[] = { 15,18,19,25,28,34,65,49,27,37 };
	int a[] = { 65,100,70,32,50,60 };
	HP hp;
	HeapInit(&hp);

	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);    //依次插入，插入完成后就是堆的形状
	}

	
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    打印结果
    在这里插入图片描述
    在这里插入图片描述

    1. 从打印结果来看，堆顶元素32被删除了，堆的最终形状依然维持着小根堆的形状。

    3.3.6 返回堆顶元素

    HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    1. 直接将堆顶元素return就行

    在主函数中调用返回堆顶元素函数

    int main()
{
	//int a[] = { 15,18,19,25,28,34,65,49,27,37 };
	int a[] = { 65,100,70,32,50,60 };
	HP hp;
	HeapInit(&hp);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);    //依次插入，插入完成后就是堆的形状
	}

	
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	printf("%d ",HeapTop(&hp));

	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    打印结果
    在这里插入图片描述

    1. 堆顶元素50被返回。

    3.3.7 销毁堆

    void HeapDestroy(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    1. 因为储存堆中元素的数组是动态开辟的，所以将数组free掉，再直接置空。
    2. 数组为空后，再将表示堆当前的实际大小与堆的容量赋值为0.

    在主函数中调用销毁堆的函数

    int main()
{
	//int a[] = { 15,18,19,25,28,34,65,49,27,37 };
	int a[] = { 65,100,70,32,50,60 };
	HP hp;
	HeapInit(&hp);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);    //依次插入，插入完成后就是堆的形状
	}

	
	HeapPrint(&hp);

	HeapDestroy(&hp);
	HeapPrint(&hp);

	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    打印结果
    在这里插入图片描述

    1. 可以看到，当堆被销毁后，再次调用打印堆函数，打印函数中断言出现警告，说明堆中已无元素。

    3.3.8计算堆当前储存元素个数

    //返回堆当前存储数据的个数
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    在主函数中调用

    int main()
{
	//int a[] = { 15,18,19,25,28,34,65,49,27,37 };
	int a[] = { 65,100,70,32,50,60 };
	HP hp;
	HeapInit(&hp);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);    //依次插入，插入完成后就是堆的形状
	}

	
	HeapPrint(&hp);

	int z = HeapSize(&hp);
	printf("%d\n", z);

	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    打印结果
    在这里插入图片描述

    3.4堆的完整代码

    Heap.h部分：包含了库函数的头文件以及自定义函数的声明。

    #pragma once

#include 
#include 
#include 
#include 

//堆是完全二叉树
//堆的二叉树用数组表示，在数组的顺序从上至下，从左至右
//小根堆，任何节点的值小于等于孩子的值
//大根堆，任何节点的值大于等于孩子的值
//数组下标计算父子关系的公式
//leftchild = parent*2 + 1   左孩子的数组下标都是奇数
//rightchild = parent*2 + 2  右孩子的数组下标都是偶数
//parent = (child - 1)/2



//创建一个小根堆，小根堆的具体实现在插入函数中引用的向上调整函数，以此不断插入就能创建堆
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;   //堆用数组实现，创建一个整形数组用来存放堆的数据
	int size;        //堆当前的实际大小
	int capacity;    //堆的容量
}HP;

//初始化堆
void HeapInit(HP* php);

//打印堆
void HeapPrint(HP* php);

//销毁堆
void HeapDestroy(HP* php);

//插入x以后依然保持堆的形状
void HeapPush(HP* php, HPDataType x);  

//向上调整
void AdjustUp(HPDataType* a, int child);

//向下调整
void AdjustDown(HPDataType* a, int n, int parent);

//删除堆顶的元素
void HeapPop(HP* php);

//返回堆顶的元素
HPDataType HeapTop(HP* php);

//判空函数
bool HeapEmpty(HP* php);

//返回堆当前存储数据的个数
int HeapSize(HP* php);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56

    Heap.c部分：实现各自定义函数的功能。

    #define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"


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

}

//打印堆
void HeapPrint(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

//销毁堆
void HeapDestroy(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

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)   //孩子的下标等于0时，说明堆从最后一个数一路向上比较，已经到达堆顶了
	{
		//小根堆，任意孩子的值要大于父节点的值，不是的话则要向上调整
		if (a[child] < a[parent])   //改为>，这个堆结构就成为大堆了
		{
			Swap(&a[child], &a[parent]);

			//修正父亲与孩子的下标，通过循环不断比较，直到成为堆的形状
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//插入x以后依然保持堆的形状
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, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("ralloc fail");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	//扩容完后将数据插入到堆的最后一个位置（数组的最后一个位置）
	php->a[php->size] = x;
	php->size++;

	//将插入的数据根据情况向上调整
	AdjustUp(php->a, php->size - 1);  //将数组和数组中最后一个数的下标传过去
}

//向下调整函数
void AdjustDown(HPDataType* a, int n, int parent)
{
	int minChild = parent * 2 + 1; //先默认左边的孩子是整个小根堆中次小的孩子
	while (minChild < n)
	{
		//与右孩子比较一下，找出小的那个孩子的下标
		if (minChild + 1 < n && a[minChild + 1] < a[minChild])
		{
			minChild++;
		}
		//找到次小的孩子后将其与父节点比较
		if (a[minChild] < a[parent])
		{
			Swap(&a[minChild], &a[parent]);
		    //修正父亲与孩子的下标，通过循环不断比较，直到成为堆的形状
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
	
}

//删除堆顶的元素 --找次大或者次小，小堆找次小，大堆找次大
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	//将堆顶元素与堆中最后一个元素交换，然后将最后一个元素删除，这样堆顶元素就被删除了。
	Swap(&(php->a[0]), &(php->a[php->size - 1]));
	php->size--;

	//向下调整，对于小根堆来说，找到次小元素，将其作为堆的堆顶，然后向下不断调整，恢复之前小根堆的形状。
	AdjustDown(php->a, php->size, 0);
}

//返回堆顶的元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

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

//返回堆当前存储数据的个数
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157

    Test.c部分：主函数放在这，在主函数中调用个函数。在实现各函数时，可以用来测试各函数的功能。

    #define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

int main()
{
	//int a[] = { 15,18,19,25,28,34,65,49,27,37 };
	int a[] = { 65,100,70,32,50,60 };
	HP hp;
	HeapInit(&hp);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);    //依次插入，插入完成后就是堆的形状
	}

	
	HeapPrint(&hp);

	int z = HeapSize(&hp);
	printf("%d\n", z);

	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
  • 相关阅读:
    【在英伟达nvidia的jetson-orin-nx和PC电脑ubuntu20.04上-装配ESP32开发调试环境-基础测试】
    项目实战-day1.0
    Linux多线程
    第55节—— redux-toolkit中的createReducer——了解
    “Java基础全方位解析，从入门到精通“
    okcc坐席进线太慢，怎么办？
    当区块链背离了它的技术本质，其充当的就只是一个概念的外衣而已
    【狂神】MyBatisPlus笔记
    一文搞定异步爬虫框架Scrapy环境的安装
    【已解决】Failed to find Ceres - Found Eigen dependency
  • 原文地址：https://blog.csdn.net/weixin_44930735/article/details/127898773