二叉树和堆

什么是树

树：树与前面的顺序表、单链表不一样，树是一个非线性结构，它可能存在着1对多的情况，不想线性表那样具有一对一的关系；
说简单点，我们可以想象一下生活中的树是啥样子的，我们数据结构里面的树就是啥样子的：

只不过这是我们的逻辑结构，帮助我们理解的，但是底层上的话，可能还是顺序表或者链表；

树的一些专业术语

既然我们已经简单了解了啥子是树，我们先来了解一下一些关于树的专业术语：

节点的度： 就是一个节点下面连接着几个节点，比如上图中的A连接着B、C、D这3个节点，那么A的度就是3；同理J的度就是0，它下面也没有链接其他节点嘛；
叶子节点： 也就是度为0的节点，比如J、K、L等都是叶子节点；
分支节点： 也就是度不为0的节点，比如上述的E、E、G、H;
双亲节点： 比如图中G节点，它的上一个节点是C与其直接相连，那么C节点就叫做G的双亲节点；
孩子节点： 还是G节点，刚才说了C是它的双亲节点，那么反过来站在C节点的角度，G节点就是C节点的孩子节点；孩子节点也就类似于这样关系；
兄弟节点： 就比如同一层节点都是彼此的兄弟节点，比如F的兄弟节点是E或者G、H；
树的度： 我们知道一颗树中每个节点都有自己的度，那么度最大的那个节点的度，就代表这整颗树的度；
节点的层次： 以根节点为第一层，其孩子节点为第二层依次类推；
树的高度： 通常我们把根节点作为高度为1来算，每增加一个层次，树的高度就增加1，空树的高度通常用0来表示（有的地方喜欢用-1来表示），比如上面这颗树的高度就是：4；
堂兄弟节点： 就比如F节点，E节点就是它的亲兄弟节点，G节点就是它的堂兄弟节点；
节点的祖先： 从根节点到到该节点，所经过的所有节点都是该节点的祖先；（根节点是所有节点的祖先）；
子孙： 从当前节点到目标节点所经过的节点都是当前节点的子孙；（所有节点都是根节点的子孙）；
森林： 多克不相交的树的集合叫做森林；

树的表示

由于树的每个节点的度不是相同，所以我们没办法想顺序表和单链表一样，设计它的数据结构；如果我们按照节点的度最大的方法来设计数据结构，那么我势必会造成空间浪费，但是我们如果不这样做的话，又不能完整的表示其连接关系和保存其数据，为此有大佬专门设计了一个NB的方案来解决这个问题：

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

该方法叫做孩子兄弟表示法：
画个图示意一下：

通常情况我们用该节点的左指针域存该节点的第一个孩子，利用该节点的右指针域存储离其最近的亲兄弟，注意！！！这里是说的亲兄弟，不是表兄弟！！！
有了这么个NB的设计那么树这种数据结构就能够很好的被计算机保存下来：
就比如下图：有了双面的结构，我们就可以对其转换：

经过转换过后得到如图：

我们可以发现这是一颗度为2的树！！也就是我们耳熟能详的二叉树！！！
这样一来的话，我们不就很好的将上述数据存储在计算机当中了嘛！空间浪费也是比较小了！！同时这也说明了我们为什么要学习二叉树的原因了！！，通过上面的那个结构定义我们可以知道任何一颗树或者森林都能通过孩子兄弟表示法转换为一颗二叉树！！
由此可见当时提出这个设计的人是多么的牛！！！

二叉树的概念

上面再阐述结构设计的时候讲了我们为什么会着重讲解二叉树而不是三叉树、四叉树的一个重要原因；
还有一个原因就是利用二叉树存储的话我们可以将空间浪费降到最小！！

什么是二叉树

概念：就是度为2的树！

现实中的二叉树：

特殊的二叉树

**满二叉树：**一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
比如下图：

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

要注意其连续性！！！

同时我们需要注意，满二叉树是一颗特殊的完全二叉树！！！

二叉树的性质

1、若规定根节点的层数是1，则第i层的节点数最多为2^(i-1)个（i>=1）;
2、若规定根节点的层数是1,假设一颗树的深度为h，那么这颗树最多有2^h-1个节点；
3、对于任何一颗二叉树来说，假设其叶子节点的个数为n0,度为1的节点的个数为n1，度为2的节点个数为n2；那么总节点的个数为：n0+n1+n2;同时还有一条特别重要的结论：n0=n2+1；
4、若规定根节点的层数为1，具有n个结点的满二叉树的深度 $\log (N+1)$(其中$\log$表示以2为底的对数)；
5、对具有n个节点的完全二叉树，我们现在从根节点（根节点标为0）开始从左往右S形给每个节点标号！（标号范围0~N-1），那么假设一个节点的标号为i，则：
该节点的父亲节点为标号为：（i-1)/2的节点；
其左孩子节点为标号为：2*i+1的节点；
其右孩子节点为标号为：2*i+2的节点；

堆的概念

堆： 如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
其中:
1、所有父节点的值都大于等于子节点的值，叫做大堆；
比如：

2、所有父节点的值都小于等于子节点的值，叫做小堆；
比如：

3、任何一个数组一定数完全二叉树，但是不一定是一个堆！

堆的表示方式

堆一般是用数组来表示的，但是也是有链式结构的表示方法的，但是我们今天只讲解数组实现的堆！！

其中上图的有侧部分才是我们堆在内存中的真实模样，右边只是我们想象出来的，方便我们人理解的！！所以它叫做逻辑图！！！数组才是其物理存储方式！！

堆的实现

堆作为一种数据结构，主要实现以下几个功能：

刚才说了我们主要采用数组来实现堆，为此对其设计的数据结构为：

堆的初始化及销毁

刚开始什么也没有，那么该置空的置空，该置0的置0；
堆的初始化：

//堆的初始化
void HeapInit(Hp* php)
{
	assert(php);
	php->Capcity = 0;
	php->nums = NULL;
	php->size = 0;
}
1
2
3
4
5
6
7
8

堆的销毁：

//堆的销毁
void HeapDestroy(Hp* php)
{
	assert(php);
	free(php->nums);
	php->Capcity = 0;
	php->size = 0;
}
1
2
3
4
5
6
7
8

堆的插入

首先我们插入一个数据过后任然要保持该结构是一个堆，不能破环堆的这种结构：
比如：（我们想要建立一个大堆）

现在红色部分之前都是一个大堆，那么我们现在插入一个3过后任然要保持该结构是一个大堆，不能打乱其结构，不然就没有意义了！！
现在我插入的是3对吧，那么现在插入过后这个结构还是个堆，我们没有打乱其结构，就不需要对这个结构做任何处理；那么我们是如何判断插入3过后还能保持一个大堆的嘞！首先大堆的定义就是要求所有父节点的值要大于等于孩子节点的值，那么现在3（已经插入数据）的父节点根据公式（i-1）/2，不就是30嘛，现在30大于3，那么插入3过后该结构还能保持大堆的结构；
但是如果我们插入的是100，

那么很明显，该结构就不再是大堆，因为100的父节点才30，100大于30孩子节点的值大于了父节点的值，不能再保证原结构是一个大堆结构了，为此我们需要向上调整，交换父亲和孩子节点的值：

这样一看局部已经满足大堆了，但是全局来看该结构任然不是一个大堆，我们就继续向上调整：

我们再判断一下此时孩子节点的值和父节点的值谁大谁小：
不出意味的话我们又要向上调整：

经过该次调整过后就不需要在调整了，因为child已经来到了根节点，没有父节点了，为此停下调整；
代码实现：

static void Swap(HPDateType* p1, HPDateType* p2)
{
	HPDateType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//扩容
static void Check_Capcity(Hp*php)
{
	assert(php);
	//容量满
	if (php->size == php->Capcity)
	{
		int NewCapcity = php->Capcity == 0 ? 4 : php->Capcity * 2;
		HPDateType* tmp = (HPDateType*)realloc(php->nums,sizeof(HPDateType)*NewCapcity);
		if (!tmp)
			exit(EXIT_FAILURE);
		php->nums = tmp;
		php->Capcity = NewCapcity;
	}
}
static void AdjustUp(HPDateType* nums, int size, int child)//向上调整
{
	 child = size - 1;
	int parent = (size - 2) / 2;
	while (child > 0)
	{
		parent = (child - 1) / 2;
		if (nums[child] <nums[parent])//说明插入数据不能保持堆是一个大堆，需要调整
		{
			Swap(nums + child,nums + parent);
			child = parent;
		}
		else
			break;
	}
}
//堆的插入
void HeapPush(Hp* php, HPDateType x)
{
	assert(php);
	Check_Capcity(php);
	php->nums[php->size] = x;
	php->size++;
	AdjustUp(php->nums,php->size,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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

时间复杂度O（logN）

堆的删除

堆的删除不是删除堆底节点，而是删除堆顶节点！！！同时再删除堆顶节点过后我们仍要保持该结构是一个堆！！！；
为此我们不能简单将后面的数据往前挪，因为这样会打乱其堆的属性，同时时间复杂度也很高！！

很显然堆的结构会被破环掉；
为此我们不能这样改，首先我们发现就算删除了堆顶元素的话，左子树和右子树也是一个堆对吧，为此我们可以将堆顶元素和队尾元素交换位置，就变为了：

那么现在我size（记录有效元素个数的变量–）是不是就删除了堆顶元素！！

那么现在我绿色圈起来的才是真正的有效元素，我闷先再要将他调整为堆，我们可以采用向下调整的算法！从堆顶开始，如果左右孩子中的最大值大于父亲节点的话，则交换这两节点之间的内容：

现在11，小于13那么交换，同时交换完毕过后更新parent和child

现在parent已经没有孩子了，则说明不需要向下调整了，现在我们发现整棵树就被调整成了大堆：
代码实现：

}
static void AdjustDown(HPDateType* nums, int size)//向下调整
{
	int parent = 0;
	int child = 2 * parent + 1;//假设左孩子是两个孩子之间最大的;
	while (child < size)
	{
		//验证假设对不对
		if (child <size - 1 &&nums[child + 1] <nums[child])//不满足假设需要调整
		{
			child++;
		}
		if (nums[parent] >nums[child])//说明不满足大堆需要调整
		{
			Swap(nums + parent, nums + child);
			parent = child;
			child = 2 * parent + 1;
		}
		else//满足大堆
			break;
	}
}
//堆的删除
void HeapPop(Hp* php)
{
	assert(php);
	assert(HeapEmpty(php)==false);
	Swap(php->nums,php->nums+php->size-1);
	php->size--;
	AdjustDown(php->nums,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

时间复杂度为log(N)

堆的判空与获取堆顶元素

//获取堆顶数据
HPDateType HeapTop(Hp* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->nums[0];
}
//获取堆的元素个数
int HeapSize(Hp* php)
{
	assert(php);
	return php->size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

堆的主要应用

堆排序

堆排序想比大家一定听说过它吧！是一个比较快的排序！
我们通过上面的了解到，堆主要有两种：大堆和小堆；

我们以大堆来讨论（小堆也是一样的）
堆排序的第一件事就是建堆！！！这很重要！！
那么建堆嘞主要有三种方式！

利用堆数据结构建堆

就比如我们现在想要堆这段数据进行建大堆，第一种方法我们直接利用HeapPush将数组的每个元素建立起堆来，我们只管给数据进行，HeapPush会自动帮我们调整大堆，并时刻让插入的数在合适的位置！代码方面就是：

	Hp hp;
	HeapInit(&hp);
	int arr[] = { 20,1,11,29,38,40,2,4,0,53 };
	int len = sizeof(arr) / sizeof(int);
	for (int i = 0; i < len; i++)
	{
		HeapPush(&hp,arr[i]);
	}
1
2
3
4
5
6
7
8

运行截图：

我们可以发现已经成功建立起堆了，我们离完成目标就不远了；
现在大堆的堆顶的元素是不是就是整个数组最大的，那么现在好我们现在取其堆顶元素，然后将其放回原数组（如果想排升序的话就从后往前放，降序的话从头开始放）假设我们想排升序：

那么对顶元素是不是就该删除了，他已经没有作用了，然后嘞我们同时调用HeapPop来帮助我们完成这个删除操作，在删除的过程中HeapPop函数会帮我们在重新建立大堆，那么我们接下来只需重复上面的步骤即可，当堆里面的元素个数为0时就说明元素已经取光了，可以结束了：
代码反面就是：

Hp hp;
	HeapInit(&hp);
	int arr[] = { 20,1,11,29,38,40,2,4,0,53 };
	int len = sizeof(arr) / sizeof(int);
	//1、建堆
	for (int i = 0; i < len; i++)
	{
		HeapPush(&hp,arr[i]);
	}
	int j = len-1;
	//2、选取堆顶元素返回元素组
	while (HeapEmpty(&hp) == false)
	{
		arr[j--] = HeapTop(&hp);
		HeapPop(&hp);
	}
	for (int i = 0; i < len; i++)
	{
		printf("%d ",arr[i]);
	}
	HeapDestroy(&hp);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

成功完成升序！！
但是嘞这种方法不是很好！
1、如果我们没有堆这种数据结构的话我们还需要自己去写，很不方便；
2、借用堆这个数据结构空间复杂度比较高！；

利用向上调整算法来建堆

其实上面的过程我们也都大致了解了一下，最主要的操作就是建堆，
现在我们就利用一下向上调整算法建一建堆：
向上调整建堆的前提是：待调整数据的前面必须是堆！！！
向上调整算法的实现我们前文已经讲解过了，这里就不在罗嗦了，我们主要讲解如何利用向上调整算法建堆！！
那到底是啥意思了：

至此以上便是利用向上调整算法建堆的大致过程！由于我们就是在原数组的基础上建的大堆，我们并没有额外开销空间，所以空间复杂度就是O（1）；
代码方面就是：

int arr[] = { 20,1,11,29,38,40,2,4,0,53 };
	int len = sizeof(arr) / sizeof(int);
	//1、利用向下调整算法建堆：
	for (int i = 0; i < len; i++)
	{
		AdjustUp1(arr,i+1);
	}
1
2
3
4
5
6
7

显然这是一个大堆！
那么现在我们为了排序嘞，我们就得模拟一下HeapPop的实现过程，主要是将堆顶元素与堆顶元素交换一下位置，那么数组的最大值是不是在在数组最末尾去了，然后我们有效元素个数减1，此时左子树、右子树是个大堆，我们现在要对对顶元素重新调整，那么就只需执行向下调整算法就好了：

然后我们只需要重复上面的过程即可：
代码方面：

int arr[] = { 20,1,11,29,38,40,2,4,0,53 };
	int len = sizeof(arr) / sizeof(int);
	//1、利用向上调整算法建堆：
	for (int i = 0; i < len; i++)
	{
		Adjustup1(arr, i + 1);
	}
	//2、开始选数排序
	int size = len;
	while (size > 1)
	{
		Swap(arr,arr+size-1);
		size--;
		AdjustDown1(arr,0,size);
	}
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

利用向下调整算法建堆

向下调整算法建堆的前提就是：左右子树都必须是堆，为此我们可以从最后一个叶子节点的父节点开始向下调整，因为每个叶子节点即可以认为是大堆，也可以认为是小堆，调不调都没啥变化！！

代码实现：

	int arr[] = { 20,1,11,29,38,40,2,4,0,53 };
	int len = sizeof(arr) / sizeof(int);
	//1、利用向下调整算法建堆：
	for (int i =(len-1-1)/2; i>=0; i--)
	{
		AdjustDown1(arr, i,len);
	}
	//2、开始选数排序
	int size = len;
	while (size > 1)
	{
		Swap(arr,arr+size-1);
		size--;
		AdjustDown1(arr,0,size);
	}
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

那么利用向下调整算法和向上调整算法，那个方法建堆更好嘞？
我们先证明向下调整算法建堆，向上调整算法时间复杂度计算是一样的：
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此：建堆的时间复杂度为O(N)。
向上调整算法建堆时间复杂度的计算也是如此，只不过计算出来时间复杂度是O（NlogN）比我们的向下调整算法满很多，所以我们的堆排序也是通常采用向下调整的算法建堆；

TopK问题

也就是类似于筛选出国服韩信前10的玩家、月考前10的学生、时间富豪前10的问题；
这些都是TopK问题；
解决这类办法的主要思路：

1、 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
这里我们来解释一下为什么选前K个最大元素建小堆
我们可以这样想，假设现在题目要求我们要选前k个最大的；
那么我们可以不可就假设我的前K个元素就是我要找的最大的k个元素嘞，但是为了以防万一，我得检查一遍我的假设啊！如果假设成立的话，那么一定有前k个元素的最小值都是>=剩余n-k个元素中的任意一个值的，如果n-k个元素中只要有一个元素不满足这种关系，那么我么的假设就出问题了，说明我们假设的前k个元素是最大的结论是错误的，现在出现了比前k个元素中的最小值还要大的元素的，那么现在我们就需要更正我们的假设，将原先最大的k个元素的最小值交换出去，把比它大的元素交换进来，就好比我原来假设的是前k个最大，那么前k个的和也一定是最大的，那么说现在我发现我的假设错误了，我发现我前k个的和可以更大，那么为了变大，我们自然愿意去牺牲最小的然后换取较大的数进来，这么说应该是讲解清楚了！，然后重新选出最小值，继续验证我们的假设！而这个重新选出最小值的过程也就是我们建立小堆的过程！！（时间复杂度为logK，速度很快），这样是我们为什么选择前k个最大的数，会将前k个数建成小堆的原因！！！

下面我们来做到例题感受一下：

分析：
首先这是需要我们求解前k个最小值，那么
1、前k个元素建立大堆；
2、如果发现前k个元素的最大值大于我的n-k中的元素的某一个元素，将这个最大值替换出去，将比其小的值送进来，然后再利用向下调整算法，重新计算出准备献祭的下一个元素！！

代码实现：

 void AdjustDown(int*nums,int top,int end)//向下调整算法
 {
      int parent=top;
      int child=2*parent+1;
      while(child<end)
      {
          if(child+1<end&&nums[child+1]>nums[child])
          child++;
          if(nums[parent]<nums[child])
          {
              int tmp=nums[parent];
              nums[parent]=nums[child];
              nums[child]=tmp;
              parent=child;
              child=2*parent+1;
          }
          else
          break;
      }
 }
int* smallestK(int* arr, int arrSize, int k, int* returnSize){
            for(int top=(k-1-1)/2;top>=0;top--)//1、前k个元素先建堆
            AdjustDown(arr,top,k);
            for(int j=k;j<arrSize;j++)
            {
                if(arr[j]<arr[0])//开始验证假设
                {
                    int rmp=arr[0];
                    arr[0]=arr[j];
                    arr[j]=rmp;
                    AdjustDown(arr,0,k);
                }
            }
            *returnSize=k;
            return arr;
}
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

时间复杂度：O（N）
空间复杂度：O（1）