树+二叉树 详解 详解 +Top-k问题_二叉树 top k问题

树相关介绍介绍

这是树！
我们数据结构中的树是现实树的倒过来，像这样

所以树可以看作除根节点以外的子树的集合，因此，树是可以递归定义的！
树的表示方法挺多，例如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等
但是最好的是孩子兄弟表示法：简单来说就是父节点的下一个指针只会指向第一个孩子，然后第一个孩子指向它的兄弟节点，一层管一层，类似于父亲只负责管老大，然后老大管着老二，依次套娃下去

类似于这样

在这我不过多赘述，（我只是陈述一下树，二叉树才是硬菜）再强调一点：树形结构中，子树之间不能有交集，否则就不是树形结构。

注：相关阐述参考第一张截图 上上张图
节点的度：节点有几个孩子度就是几，如最上面的图中，节点A的度是6
叶子（也叫终端节点）：就是没有孩子的最后的节点，例如P Q H等
双亲节点或父节点：举个例子A是的父节点，E是I的父节点
树的度：一棵树中，最大节点的度就是这棵树的度，上图中树的度就是6
节点的层次;从根节点开始定义，一般是从1开始（有时从0开始）
树的高度或深度：上图中树的深度就是4
兄弟节点：公用一个父节点
森林：由m（m>0）棵互不相交的树的集合称为森林

二叉树相关介绍

二叉树是特别的树！

概念：1，或者为空节点
2… 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
例如：

顾名思义：每个父节点最多两个孩子
注：由于二叉树有左右之分，所以二叉树是有序树
提示提示：重点来了！！！
特殊的二叉树（我简单概括一下）
满二叉树：就是每个节点都有两个子节点
完全二叉树：假设有k层，前k-1层都是满二叉树，但是最后一层不是满的，但从左往右的节点都是连续的


二叉树的性质
虽然很枯燥，但还是得坚持看完啊hh

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1 .
3. 对任何一棵二叉树, 如果度为N0其叶结点个数为 , 度为2的分支结点个数为 N2,则有 N0＝ N2＋1(可能例子不够形象，自己动手吧！！）

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1) . (ps： 是log以2为底，n+1为对数）
   根据：2^(h-1) = n 可以算出答案

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号（这也符合之前的一句话，二叉树是区分左右子树的，是有序树！）
   
   观察图我们可以发现，如果该节点序号为i且有子节点，那么其
   左孩子 = 2i+1;右孩子：2i+2；
   除根结点外，每个节点（序号为k），其父节点都可以用(k-1)/2
   因为在C语言中是向下取整，所以都可以用这个公式表示

堆

二叉树的存储方式一般有两种，顺序存储和链式存储，后者属于高阶数据结构，我不过多阐述。
顺序存储结构在二叉树中一般只用于存储完全二叉树，因为完全二叉树如果按照序号标的话是连续的，符合我们上边讲的，子节点与父节点的关系，其他的二叉树会有空间上的浪费。举个例子吧

然后我们把这种逻辑上看作二叉树，实际上是一个数组的这种结构称为堆（当然，满二叉树是特殊的完全二叉树，也符合堆的性质）
注：需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。（类似于“栈”一样的）
堆的分类：
大根堆：就是每棵字数，父节点一定大于子节点，所以一棵二叉树，其根节点是这棵树的最大值，但是注意：只是满足父节点比子节点大，兄弟节点之间的关系是不确定的

小根堆：同理，只不过是要求其父节点都小于子节，每棵树的根节点都是这棵树的最小值，兄弟节点之间的大小关系不确定。

呼~~~结束了终于开始代码了
我写的是大根堆

#pragma once;
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;//表示堆中有效元素的个数
	size_t capacity;//表示堆的容量

}HP;
void Swap(HPDataType* pa, HPDataType* pb);//交换两个数字
void HeapInti(HP* php);//堆的初始化
void HeapDestory(HP* php);//堆的销毁
void HeapPrint(HP* php);//堆的打印
bool HeapEmpty(HP* php);//判断堆是否为空
size_t HeapSize(HP* php);//返回堆中元素的个数
HPDataType HeapTop(HP* php);//返回堆顶的元素
void HeapPush(HP* php, HPDataType x);//插入x后维持大小堆
void HeapPop(HP* php);//删除堆顶的数据，同时维持大小堆
void AdjustUp(HPDataType* a, size_t child);//从徐海为child开始向上调整
void AdjustDown(HPDataType* a, size_t size, size_t root);//


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

先用代码写一下简单函数
注意关键：我们的逻辑结构是二叉树，但是物理结构是数组

#include"Heap.h"
void Swap(HPDataType* pa, HPDataType* pb)//交换两个数字
{ 
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}


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

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


}


void HeapPrint(HP* php)//堆的打印
{
	assert(php);
	for (int 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];
}
//建大堆
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

向上调整：
思路：自下而上（不一定调整到顶）
这个函数是在我们在最后面插入一个数字再用的，我们在数组后面插入一个数字后，假设原来的数组有k个元素，插入后有k+1个元素,那么前k个元素肯定是符合大/小堆的，所以我们从第k+1个元素开始，自下而上开始调整，最终调整到是的k+1个元素都符合大/小堆

堆的插入如下图

//建大堆
void AdjustUp(HPDataType* a, size_t child)//从徐海为child开始向上调整
{
	size_t parent = (child - 1) / 2;//这是根据公式推出来的
	while (child > 0)//当child为0的时候循环便截至
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}



	}

}
void HeapPush(HP* php, HPDataType x)//插入x后维持大小堆
{
	assert(php);
	//插入之前要先判断堆是否满
	if (php->capacity == php->size)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		//HP* tam = (HP*)malloc(sizeof(HP) * newCapacity);
		HP* tam = (HP*)realloc(php->a, sizeof(HP) * newCapacity);//这边一定要用realloc
		                //是在原有的php->a上进行扩容,所以用realloc

		if (tam == NULL)
		{
			printf("malloc fail\n");
			exit(-1);
		}
		php->a = tam;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);//在最后的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

**向下调整：**自上而下（不一定调到底）
需要的条件,必须保持除要调节的节点之外其他两个子树是符合大/小堆排序的
举个例子，假设我们每次都要删除堆顶的元素，那么我们每次将堆顶的元素与堆低的元素交换，接着从堆顶开始向下调整即可，假设原来有k+1个元素，我们把堆顶与堆底元素交换之后，再让size–。那么此时堆顶元素就被删除了，但是此时的堆顶元素是原来的堆底元素，所以现在有k个元素了，接着，除去现在的堆顶元素，其他的元素都是符合大/小堆的,这个时候再从根节点开始向下调整即可。

堆的删除如下图
注意：删除的话不能除堆顶后的元素依次往前挪，不说时间复杂度是O（n）
而且破坏了堆的结构!

void AdjustDown(HPDataType* a, size_t size, size_t root)//向下调整,条件是其他子树必须是大/小堆
{                              //表示数组的元素个数 root表示从哪一个序号开始调整
	                          //root不一定就是根节点
	size_t parent = root;
	size_t child = parent * 2 + 1;//child先表示左孩子
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child])
		{
			//因为右孩子可能不存在，而左孩子加1表示右孩子
			//当右孩子的序号小于size时表示存在，而第二个条件是，我们要找出左右孩子的最大值
			//确保child中的序号就是最大值，然后只需要比较a[child]和a[parent]
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
         
}

void HeapPop(HP* php)//删除堆顶的数据，同时维持大小堆
{
	assert(php);
	//思路,先将堆顶元素和最后一个元素交换位置
	//然后Pop掉最后一个元素,然后再向下调整一下
	//因为此时除了堆顶元素外，其他两个子树都是符合大/小堆的
	assert(php->size > 0);
	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
41
42

堆排序（初级）

堆排序其实就是用堆这个数据结构来给数组排序
我接下来要写的是一个堆降序的一个算法。
思路：假设需要排序的数组位arr，然后额外开一个数组s
我们先建一个大根堆，先将栈顶的元素赋予s,接着删除栈顶元素，再把下一个栈顶元素赋予给s直到跳出循环

int arr[] = { 2,4,5,7,9,10,25,77,88,99 };
	int s[20] = { 0 };
	int k = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	HP sp;
	HeapInti(&sp);
	for (int i = 0; i < sz; i++)
		HeapPush(&sp, arr[i]);
	while (!HeapEmpty(&sp))//当堆中的元素大于0的时候
	{
		s[k++] = HeapTop(&sp);
		HeapPop(&sp);
	}
	for (int i = 0; i < k; i++)
		printf("%d ", s[i]);

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

反思这个算法好吗？时间复杂度（n*logn）
不讨论时间复杂度，我们写一个数组的排序，还得写一个堆，然后完了还得写额外数组来收原来的数组，空间复杂度是O（n），所以这并不是一个好的算法，那么能不能写出空间复杂度是O(1)的算法，但是时间复杂度不变的？

堆排序（优化）

我们先思考一下，堆是什么？它的物理结构是数组，逻辑结构是二叉树，那么我们能不能直接再数组上操作呢？并且根据数组排序？
整体思路：
升序：建大堆
降序：建小堆
思路：
假设我们现在要写一个升序的算法
假设现在数组就是一个大堆的排序情况，然后我们将数组的第一个数字与最后一个数字交换，然后size-1，接着从第一个数字开始调整，一直这样，直到size = 0
反之降序，建小堆也是这样的
如何直接用数组建堆？
1.使用向上调整，插入数据的思想建堆
假设堆一开始就是数组的第一个元素，然后循环插入，直到完全插完，这个比较好理解
2.使用向下调整
向下调整比较麻烦因为它需要一个条件：除了需要调整的那个根结点外，其他两个子树必须是满足大/小堆的排序的

所以此时如果和向上调整一样操作的话肯定是有点问题的，因为向下调整必须保持结构符合上述。
因此，我们反其道而行之，从最后一个叶子的根节点开始向下调整

按照这个顺序，依次进行调整
好啦，思路结束了，开始代码~~~

向上调整：

int arr[] = { 2,4,5,7,9,10,25,77,88,99 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (int i = 1; i < sz; i++)
	{
		AdjustUp(arr, i);
	}
	for (int i = 0; i < sz; i++)
		printf("%d ", arr[i]);

1
2
3
4
5
6
7
8
9

向下调整：

int arr[] = { 2,4,5,7,9,10,25,77,88,99 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//循环是从(sz-1-1)/2开始的
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)//注意这个时候向下调整
	                                           //一定要直到根节点0
	{
		AdjustDown(arr, sz, i);//表示此时以i位根节点向下调整。

	}
	for (int i = 0; i < sz; i++)
		printf("%d ", arr[i]);

1
2
3
4
5
6
7
8
9
10
11
12

建好堆了，再来思考那句话，升序建设大堆，降序小堆
以我代码里面的数组为例：
此时建好的大堆是

然后我们此时要写的是升序的算法，注意：大堆只能算出最大值也就是堆顶，不能算出次大值，我们现在

然后除去最后一个后接着调整前k-1个数字 一直这样，就可以直接实现数组排序了

int arr[] = { 2,4,5,7,9,10,25,77,88,99 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//循环是从(sz-1-1)/2开始的
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)//注意这个时候向下调整一定要直到根节点0
	{
		AdjustDown(arr, sz, i);//表示此时以i位根节点向下调整。

	}
	//现在已经建好堆了
	for (int i = sz - 1; i > 0; i--)
	{
		Swap(&arr[0], &arr[i]);
		AdjustDown(arr, i, 0);

	}


	for (int i = 0; i < sz; i++)
		printf("%d ", arr[i]);
	//输出值：2 4 5 7 9 10 25 77 88 99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

向上/下调整建堆时间复杂度问题

时间复杂度：我们按最坏的情况算的话就是按找满二叉树算哈。
然后算的话主要是算根节点和子节点交换的问题，不算比较左孩子与右孩子的问题

向上调整：
第一层：0次
第二层：1次
第三层：2次
…
第h层：h-1次
所以总的次数：

然后各种数学技巧
得出答案：

因为2^h-1 = n(节点总个数）
所以换算一下得出时间复杂度是O(N*logN);
同理：
向下调整建堆的时间复杂度：

TOP-K问题

先了解一下说明是TOPK问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

抓住关键：需要处理的数据比较大
因为假设数据非常大的话排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
   将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
   例如：找出下列数组中前十个最大的数字

PrintTopK(int *a, int n, int k)
{
	//先根据向上调整创建k个小堆
	int* kheap = (int*)malloc(sizeof(int) * k);
	assert(kheap);
	for (int i = 0; i < k; i++)
		kheap[i] = a[i];
	for (int i = 1; i < k; i++)
		AdjustUp(kheap, i);
	//然后遍历后面的n-k个元素，如果比堆顶元素大，那么就交换
	for (int i = k; i < n; i++)
	{
		if (a[i] > kheap[0])
		{
			kheap[0] = a[i];
			AdjustDown(kheap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
		printf("%d ", kheap[i]);

}
void TestTopk()
{
	int n = 100000;
	int* a = (int*)malloc(sizeof(int) * n);
	assert(a);
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		a[i] = rand() % 100000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2305] = 1000000 + 6;
	a[99] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[0] = 1000000 + 1000;
	PrintTopK(a, n, 10);
}

int main()
{
	TestTopk();
	//输出结果：1000001 1000003 1000002 1000007 1000005 1000006 1000004 1001000 1000009 1000008
	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
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

求赞！求关注！