Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》

欢迎点赞，关注！

1、树 

1.1 树的概念与结构

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

        有一个特殊的结点，称为根结点，根结点没有前驱结点。

         除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合 Ti( 又是⼀棵结构与树类似的子树。每棵⼦树的根结点有且只有⼀个前驱，可以 有 0 个或多个后继。因此，树是递归定义的。

1.2树的相关术语

        父结点/双亲结点：若⼀个结点含有子结点，则这个结点称为其子结点的父结点；

        子结点/孩子结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点；

        结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；

        树的度：⼀棵树中，最⼤的结点的度称为树的度；

        叶子结点/终端结点：度为 0 的结点称为叶结点；

        分支结点/非终端结点：度不为 0 的结点；

        兄弟结点：具有相同父结点的结点互称为兄弟结点(亲兄弟)；

        结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；

        树的高度或深度：树中结点的最大层次；

        路径：⼀条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；

2、二叉树

        2.1二叉树的定义

二叉树满足以下两个特点：

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

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

        2.2特殊的二叉树

        2.2.1满二叉树

        ⼀个二叉树，如果每⼀个层的结点数都达到最⼤值，则这个二叉树就是满二叉树。也就是说，如果⼀ 个二叉树的层数为 K ，且结点总数是2的k次方-1 ，则它就是满二叉树。

        2.2.2完全二叉树

        完全二叉树是效率很高的数据结构，完全二叉树是由满⼆叉树而引出来的。

        对于深度为 K 的，有 n 个 结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 至 n 的结点⼀⼀对应时称 之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。

3、堆

3.1概念

        堆（Heap）是计算机科学中的一种特殊数据结构，它可以被视为一棵完全二叉树的数组表示形式。堆的特点是节点的值总是不大于或不小于其父节点的值，这种性质使得堆的根节点总是该数据结构中的最大值或最小值。

        其中，堆的根节点是该数据结构中的最大值则称该堆为大根堆；

        堆的根节点是该数据结构中的最小值则称该堆为小根堆。

        堆满足以下特性：

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

        堆总是⼀棵完全二叉树。

 3.2堆的性质（二叉树的性质）

        对于具有 n 个结点的完全⼆叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：

        1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，无双亲结点

        2. 若 2i+1，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子

        3. 若 2i+2，右孩子序号： 2i+2 ， 2i+2>=n 否则无右孩子

4、堆的实现（动态）

4.1堆结构的定义

        size是当前有效元素个数，capacity是最大有效元素个数（容量）。

typedef struct heap
{
	int* arr;
	int capacity;
	int size;
}Heap;

4.2初始化

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->arr = NULL;
	hp->capacity = hp->size = 0;
}

4.3插入 

4.3.1插入        

void HeapPush(Heap* hp,int x)
{
	assert(hp);
	//判断空间是否已满
	if (hp->capacity == hp->size)
	{
		//注意capacity的单位是个，不是字节
		int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;//第一次开就开四个
		//空间开辟
		//注意这里是realoc不是malloc
		//所有链式结构的用malloc，咱们开辟新节点
		//所有线性结构，底层是数组的，咱们就realoc
		//因为咱们要保留数组之前的数据，所以必须要扩容而不是重新开辟
		Heap* newspace = (Heap*)realloc(hp->arr,newcapacity * sizeof(int));
		if (newspace == NULL)
		{
			perror("malloc wrong!");
			exit(1);
		}
		hp->arr = newspace;
		hp->capacity = newcapacity;
	}
	//直接插入
	//size是当前有效元素个数，对应的也是下一个该存放元素位置的下标
	hp->arr[hp->size] = x;
	hp->size++;
	//插入元素之后配套进行向上调整
	AdjustUp(hp,hp->size-1);//注意传入的是下标
}

4.3.2 向上调整算法

void AdjustUp(Heap* hp,int child)//传入堆和调整的起始孩子
{
	int parent = (child - 1) / 2;//公式
	while (child > 0)//注意退出条件
	{
		//建小根堆
		if (hp->arr[parent] > hp->arr[child])
		{
			swap(&hp->arr[parent], &hp->arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;//如果不用换了。说明这个堆正常了，和adjustdown的退出原因一样
		}
	}
}

4.4判空

bool empty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

4.5删除 

4.5.1删除

void HeapPop(Heap* hp)
{
	//几乎所有的数据结构，在插入元素是要断言这个数据结构是否存在
	//在删除元素的时候断言这个数据结构中要含有元素
	assert(!empty(hp));
	//删除根元素
	swap(&hp->arr[0], &hp->arr[hp->size - 1]);
	hp->size--;
	//配套使用向下调整算法
	AdjustDown(hp, 0,hp->size);
}

4.5.2向下调整算法 

void AdjustDown(Heap* hp,int parent,int n)//n是向下调整的下界范围
{
	int child = parent * 2 + 1;//公式
	while (child<n)
	{
		//建小根堆
		if (child + 1 < n && hp->arr[child + 1] < hp->arr[child])
		{
			child++;
		}
		if (hp->arr[parent]>hp->arr[child])
		{
			swap(&hp->arr[parent], &hp->arr[child]);
			parent = child;
			child= parent * 2 + 1;
		}
		else
		{
			//我最小的孩子都比父节点大，那么这个堆就是正常堆了，直接退出
			break;
		}
	}
}

4.6取根元素 

int HeapTop(Heap* hp)
{
	assert(!empty(hp));
	//empty里面判断了这个堆必须存在，所以说不用再在这判断了、
	return hp->arr[0];
}

4.7销毁 

void HeapDestory(Heap* hp)
{
	assert(hp);
	if(hp->arr)//注意这个是在arr不为空的情况下在释放，不然free(NULL)会报错的
	{
		free(hp->arr);
	}
	hp->arr = NULL;
	hp->capacity = hp->size = 0;
}

5、堆的实现（静态）

        所谓静态实现，直白一点，就是我们不用自己取malloc一堆空间了，用空间换时间。

        底层仍然是线性结构，那我们堆的静态实现直接拿一个足够大的数组来做底层结构就OK了。

        他的建树方法是和动态实现无差别的，只是写法有稍些不同。所以我就直接把代码放在这了。所有代码包括上面的我都做了足够详细的注解。

注意以下代码我是用c++写的。

#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
int heap[N];//存放元素
int n;//标记有效元素个数
void down(int grap)
{
	int fa = grap;
	int child = fa * 2;
	
	while (child<=n)
	{
		//寻找左右孩子最大的那个
		if (child + 1 <= n && heap[child] < heap[child + 1]) child++;
		
		// 最⼤的孩⼦都⽐我⼩，说明是⼀个合法的堆 
		if (heap[child] <= heap[fa]) return;
		if(heap[child]>heap[fa])//if条件可以省去，留着方便理解
		{
			swap(heap[child], heap[fa]);	
		}
		fa = child;
		child = fa * 2;
	}
}
void up(int x)
{
	//向上调整算法与插入元素配套使用
	int child = x;
	int fa = child / 2;
	while (child != 1 && heap[fa] < heap[child])
	{
		swap(heap[fa], heap[child]);
		child = fa;
		fa = child / 2;
	}
}
void pop()
{
	swap(heap[1], heap[n]);
	n--;//删除根
	down(1);//执行向下调整算法，传入根
}

void push(int x)
{
	n++;
	heap[n] = x;//保证第一个节点下标为1

	up(n);//执行向上调整算法，传入孩子（当前节点）下标
}

int top()//堆顶元素
{
	return heap[1];
}
int size()//堆的大小
{
	return n;
}

        好了，今天的内容就分享到这，我们下期再见！