数据结构——二叉树(堆)

二叉树顺序结构以及实现

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

二叉树一般有两种结构存储: 顺序结构和链式结构。

顺序结构也就是顺序表(数组)来存储，一般只有完全二叉树和满二叉树适合数组来存储。其他二叉树会有空值——会造成空间浪费。而我们通常把堆(一种二叉树)使用顺序结构的数组来存储。

二叉树顺序存储在物理上是一个数组，在逻辑上(想象中的)是一颗二叉树。

小堆：每个父亲都小于等于孩子  parent<=child

大堆：每个父亲都大于等于孩子  parent>=child

leftchild=parent*2+1   rightchild=parent*2+2

那么parent怎么计算呢？推导一下即可

parent=(child-1)/2;

小堆(举例)

如果插入一个数据元素90 直接尾插即可 顺序表尾插效率高，而且没有破坏小堆的结构。

如果插入一个数据元素55呢？求出父亲是60

从上面情况可以看出有两种情况

1.直接插入不会影响原来堆的结构 直接尾插即可。

2.插入数据会出现比父亲小的情况(小堆)，这时候就需要去调整堆的关系，才能形成正确的堆关系，好的情况下一次调整就完成了调整，那么最坏的情况就是调整到根节点才会结束调整。

就比如下面这种情况，尾插的数据元素5直接从孙子变成了太爷爷

把数组中最后一个数据元素作为孩子，根据孩子求出父亲位置，再判断孩子是否小于父亲，如果符合条件就调整位置，再把父变子，再求父亲位置，循环以上步骤，最坏判断到根节点。

怎么判断循环结束条件呢？根据上面的画图，不难看出当parent<0 循环就结束了，但不能这样判断，因为当parent为0时 -1/2还是0 因为是除 余为0。在我们画图分析时，parent看起来会往上走，但实际还是0，因此我们要以孩子作为循环执行条件，从上面画图分析可以看出child>0时循环执行，当child==0时循环结束，因此循环执行条件应该是child>0。

说了那么多理论知识和方法，接下来开始写代码。

向上调整

void Adjustup(Heapdatatype* a, int child)
{
	int parent = (child - 1)/2;
	while (child>0)
	{
		if (a[child] >a[parent])
		{
			Swap(&a[child], &a[parent]);
 
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向上调整的前提：数据是堆

如果插入数据不符合条件break跳出循环即可

那么向下调整的时间复杂度是多少呢？深度为h的二叉树最大结点为2^h-1，假设有N个数据

那么时间复杂度就是O(logN) 如果有10亿数据也只需调整30次。

堆删除数据

那么如果堆要删除数据，怎么删呢？直接尾删吗？

把70删掉并没有实际意义，把根节点删掉才有意义

挪动覆盖大概率会打乱堆的之间的关系——形不成堆。 

那么怎么删除呢？前辈研究发现结果是——先把根节点和最后一个结点先交换，再删除 

通过根节点和最后一个结点数据交换再删除，可以发现左右子树都没有被动到，左右子树依旧是小堆。但"爷爷"隐退江湖，给孙子让位当掌门，底下的其他人坐得住吗？显然是坐不住的，因此要进行比武大会，打赢的人才有资格当下一个掌门人。

经过一系列的比武，70不出所料的又到最下面去了，德不配位了属于是。

因此向下调整的前提是：左右子树是大堆/小堆

时间复杂度也是log(N)

向下调整怎么写呢？大部分人都会先比较左右孩子(小堆为例,找出最小孩子)，再上去调整，但这样写太麻烦了，不太推荐 

向下调整

void AdjustDown(Heapdatatype*a,int n,int parent)
{
	int child = parent * 2 + 1;//默认左孩子最小
	while (child<n)
	{
		//如果假设左孩子小了是错误的 就再判断一次(找出最小孩子)
		if (a[child + 1] < a[child])
		{
			++child;
		}
		//光标闪动之处就是最小孩子位置//最小孩子 不关心是左/右子
		if (a[child] < a[parent]) 
		{
			Swap(&a[child], &a[parent]);
 
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

我们演示的是小堆的向下调整，因此我们先默认左孩子是最小的孩子，但我们的判断可能会出错误，因此在循环里面再判断一次 ，判断完成后，光标闪动的地方就是最小孩子的位置(我们不关心是左孩子最小还是右孩子最小，找出最小孩子即可)，再跟向上调整一样，判断父子之间的关系，进行调整。

从画图可以看出当child大于size循环结束，因此循环继续条件就是child小于n。

向下调整存在的问题

大家继续看看这段代码有什么bug吗？ 有的

万一右孩子不存在呢？如果右孩子不存在,child++就越界了，因为在判断条件还要补上右孩子是存在的条件。

 实验代码

int main()
{
	int arr[] = { 65,100,70,32,50,60 };
	Hp ph;
	HpInit(&ph);
	for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		//push进去以后才是堆 大堆还是小堆 具体看调整符号
        //我们建的是小堆
		HpPush(&ph,arr[i]);
	}
	HpPrint(&ph);
 
	//int k = 5;//取前5个最大的 k--走k次 --k走k-1次
	while (!HpEmpty(&ph))
	{
		printf("%d ", HpTop(&ph));
		HpPop(&ph); 
	}
	
	HpDestroy(&ph);
	return 0;
}

当push进去向上调整后，成为小堆以后，取栈顶元素再pop后，小堆变成了有序 

当是大堆时，大堆变成了降序

大堆可以依次排出降序 小堆可以依次排出升序 

但注意，目前还不算堆排序， 

如果有100家外卖店，要排出了前10个最高评分的店，是不是topk问题？根本不用一个个比较，直接把数据push进去(建堆)，再不断Top pop就可以依次取出最高/最小元素排列顺序。 

如果要取出前5个最大的 直接设一个变量 再--就可以取出来

堆排序

void HeapSort(int* a, int n)
{
		Hp ph;
		HpInit(&ph);
		for (size_t i = 0; i <n; i++)
		{
			
			HpPush(&ph,a[i]);
		}
		//HpPrint(&ph);不需要这步
		
		int i = 0;
		while (!HpEmpty(&ph))
		{
			//printf("%d ", HpTop(&ph));
			a[i++] = HpTop(&ph);//直接覆盖
 
			HpPop(&ph); 
		}
		HpDestroy(&ph);
		return 0;
}

堆排序存在问题

这个堆排序有什么缺陷呢?

1.首先我们得有个数据结构，把结构体 destroy push之类的构建出来，而且人家只需要堆排序以后的结果，不需要我们打印大堆/小堆数据，那么我们直接建立个新数组直接把堆排序结果覆盖进去。

2. 空间复杂度的消耗，数据结构申请了空间资源，因为排序额外开了新的数据空间，造成了二次空间数据空间浪费。

正确的堆排序

怎么改善堆排序呢？

直接在原数组上建堆(实际上是插入)

向上调整建堆

向上建堆的时间复杂度O(N*logN)

void HeapSort(int* a, int n)
{
	int i = 0;
	for (i = 1; i < n; i++)
	{
		Adjustup(a, i);
	}
 
}

直接在原数组上建堆，省去了push的申请空间资源，节省了空间浪费。 

如果我们要建升序 是建小堆还是大堆 

如果要升序建小堆

选出了最小的数据，要选次小，只能把剩下的数据看做堆 

但关系全乱了，剩下的数据不一定是堆，要重新建堆，建堆代价太大 时间复杂度为(N*log(N))*N

因此如果要建升序 最好是建大堆+删除思想

首尾交换 最大的数据排好了，剩下的数据向下调整，选出次大的即可。

时间复杂度是N*log(N)

向下调整建堆

向下建堆时间复杂度是O(N)

向下调整建堆会根据不同情况 有不同数据排序变化

大堆时是升序 小堆是降序 向上调整建堆一样。

因此在建堆时，向下调整建堆优势于向上调整建堆。

TopK问题

Topk问题：就是求出数据中前k个最大或最小的元素，一般情况下数据量比较大。

比如:一个游戏内全服最强前10名玩家、世界500强公司等等......

对于TopK问题，最简单的办法就是排序，建个小堆或者大堆 不断取出堆顶数据然后pop数据 就可以排出来 前k个最大或最小的元素数据(在数据量少时)，但在数据量比较大时，将所有数据全部加入内存再进行排序是不太可能的，会超过电脑本身的内存空间，造成大量的空间浪费。

因此我们就想出一下办法，在大量数据中排出前k个最大元素。

假设10亿个数据，内存存不下，数据在文件中找出最大的前K个 K==100
1.读取文件的前100个数据，在内存数组中建立一个小堆

2、再依次读取剩下数据，跟堆顶数据比较，大于堆顶，就替换它进堆，向下调整

3、所有数据读完，堆里面数据就是最大的前100个 

为什么求出前k个最大元素要建小堆？如果建立大堆，如果在N个元素中，最大的元素数据第一个就来了进堆顶，只能找出最大的一个元素，其他比它小的元素数据将进不了堆，因此不能建大堆。

而且建小堆，当我们把前100个数据元素建立好堆后，剩下的前k个最大数据元素都能进堆，因为是小堆，不会出现占在栈顶 不让其他数据元素进堆的情况，因为会向下调整。

因此Topk的空间复杂度和时间复杂度都很优秀。

时间复杂度是O(N*logK)   空间复杂度是O(K)  但这种情况都是N大于K  K都可以忽略不计

因此空间复杂度可以是O(1)  时间复杂度O(N)

Topk数据测试

 
void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
 
	for (int i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}
 
	fclose(fin);
}
 
int main()
{
	CreateNDate();
}

创造了10000个数据

void PrintTopK(const char*filename, int k)
{
	// 1. 建堆--用a中前k个元素建堆
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
 
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}
 
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
 
	//前k个数建小堆
	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(minheap, k, i);
	}
 
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			// 替换你进堆
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}
 
 
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");
 
	free(minheap);
	fclose(fout);
}
 
 
void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
 
	for (int i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}
 
	fclose(fin);
}
 
int main()
{
	//CreateNDate();
	PrintTopK("data.txt", 10);
}

但是，我们怎么知道这10个数据就是10万个数据中最大的10个数据呢？ 

我们可以在data.txt可以自己去修改随机10个数字，让他大于10万即可，再运行程序，看看结果是不是我们修改的那10个数字就可以了。

完全代码展示 

Heap.h

 
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>
typedef int Heapdatatype;
typedef struct Heap
{
	Heapdatatype* _a;
	int _capacity;
	int _sz;
}Hp;
void Swap(Heapdatatype* p1, Heapdatatype* p2);
void HpInit(Hp* ps);
void HpDestroy(Hp* ps);
void HpPush(Hp* ps, Heapdatatype x);
void HpPrint(Hp* ps);
void HpPop(Hp* ps);
bool HpEmpty(Hp* ps);
Heapdatatype HpTop(Hp* ps);
void AdjustDown(Heapdatatype* a, int n, int parent);
void Adjustup(Heapdatatype* a, int child);
void HpAryy(Hp* ps, int* a, int n);

Heap.c 

#include"Heap.h"
void HpInit(Hp* ps)
{
	assert(ps);
 
	ps->_a = NULL;
	ps->_capacity = ps->_sz = 0;
}
void HpDestroy(Hp* ps)
{
	free(ps->_a);
 
	ps->_a = NULL;
	ps->_capacity = ps->_sz == 0;
}
void HpPrint(Hp* ps)
{
	assert(ps);
 
	for (size_t i = 0; i < ps->_sz; i++)
	{
		printf("%d ", ps->_a[i]);
	}
	printf("\n");
}
void Swap(Heapdatatype* p1, Heapdatatype* p2)
{
	Heapdatatype tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void Adjustup(Heapdatatype* a, int child)
{
	int parent = (child - 1)/2;
	while (child>0)
	{
		if (a[child] >a[parent])
		{
			Swap(&a[child], &a[parent]);
 
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HpPush(Hp* ps, Heapdatatype x)
{
	assert(ps);
 
	if (ps->_sz == ps->_capacity)
	{
		int newcapcity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		Heapdatatype* tmp = (Heapdatatype*)realloc(ps->_a, sizeof(Heapdatatype) * newcapcity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->_a = tmp;
		ps->_capacity = newcapcity;
	}
	ps->_a[ps->_sz] = x;
	ps->_sz++;
 
	Adjustup(ps->_a, ps->_sz - 1);
}
void AdjustDown(Heapdatatype*a,int n,int parent)
{
	int child = parent * 2 + 1;//默认左孩子最小
	while (child<n)
	{
		//如果假设左孩子小了是错误的 就再判断一次(找出最小孩子)
		if (child + 1 < n&&a[child + 1] >a[child])
		{
			++child;
		}
		//光标闪动之处就是最小孩子位置//最小孩子 不关心是左/右子
		if (a[child]>a[parent]) 
		{
			Swap(&a[child], &a[parent]);
 
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HpAryy(Hp* ps, int* a, int n)
{
	assert(ps);
	assert(a);
 
	ps->_a = (Heapdatatype*)malloc(sizeof(Heapdatatype) * n);
	if (ps->_a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->_sz = n;
	ps->_capacity = n;
 
	memcpy(ps->_a, a, sizeof(Heapdatatype) * n);
	for (int i = 1; i < n; i++)
	{
		Adjustup(ps->_a, i);
	}
}
void HpPop(Hp* ps)
{
	assert(ps);
	assert(ps->_sz > 0);
 
	Swap(&ps->_a[0], &ps->_a[ps->_sz - 1]);
 
	ps->_sz--;
 
	AdjustDown(ps->_a,ps->_sz,0);
 
}
bool HpEmpty(Hp* ps)
{
	assert(ps);
 
	return ps->_sz == 0;
}
Heapdatatype HpTop(Hp* ps)
{
	assert(ps);
	assert(ps->_sz > 0);
 
	return ps->_a[0];
}

test.c 

#include"Heap.h"
#include<time.h>
 
//缺陷 1.首先得有一个堆的数据结构 2.空间复杂度的消耗 因为排序额外开了一段空间
//void HeapSort(int* a, int n)
//{
//		Hp ph;
//		HpInit(&ph);
//		for (size_t i = 0; i <n; i++)
//		{
//			
//			HpPush(&ph,a[i]);
//		}
//		//HpPrint(&ph);
//		//堆排要的是排序结果 不用你把原来数据打印
//		int i = 0;
//		while (!HpEmpty(&ph))
//		{
//			//printf("%d ", HpTop(&ph));
//			a[i++] = HpTop(&ph);//直接覆盖
//
//			HpPop(&ph); 
//		}
//		HpDestroy(&ph);
//		return 0;
//}
//为什么向上调整和向下调整传的不是hp 而是数组的结构 就是为了方便这里的建堆
void HeapSort(int* a, int n)
{
	//int i = 0;
	//建堆-向上调整
	//建升序 是大堆还是小堆？
	//大堆
	//for (i = 1; i < n; i++)//N*log(N)
	//{
	//	Adjustup(a, i);  
	//}
	//向下调整建堆—大堆
	//时间复杂度O(logN)
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >=0; i--)
	{
		AdjustDown(a, n, i);
	}
 
	//O（N*logN）
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
 
		AdjustDown(a, end, 0);
		--end;
	}
	
}
int main()
{
	//随便一个数组可以看成是二叉树 但不可能是堆 所以要先建堆
	int arr[] = { 65,100,70,32,50,60 };
	Hp ph;
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
	int i = 0;
	for (i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
}
//int main()
//{
//	int arr[] = { 65,100,70,32,50,60 };
//	Hp ph;
//	HpInit(&ph);
//	for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
//	{
//		//push进去以后才是堆 大堆还是小堆 具体看调整符号
//		HpPush(&ph,arr[i]);
//	}
//	HpPrint(&ph);
//
//	int k = 5;//取前5个最大的 k--走k次 --k走k-1次
//	while (!HpEmpty(&ph)&&k--)
//	{
//		printf("%d ", HpTop(&ph));
//		HpPop(&ph); 
//	}
//	
//	HpDestroy(&ph);
//	return 0;
//}
//void PrintTopK(const char*filename, int k)
//{
//	// 1. 建堆--用a中前k个元素建堆
//	FILE* fout = fopen(filename, "r");
//	if (fout == NULL)
//	{
//		perror("fopen fail");
//		return;
//	}
//
//	int* minheap = (int*)malloc(sizeof(int) * k);
//	if (minheap == NULL)
//	{
//		perror("malloc fail");
//		return;
//	}
//
//	for (int i = 0; i < k; i++)
//	{
//		fscanf(fout, "%d", &minheap[i]);
//	}
//
//	//前k个数建小堆
//	for (int i = (k - 2) / 2; i >= 0; --i)
//	{
//		AdjustDown(minheap, k, i);
//	}
//
//	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
//	int x = 0;
//	while (fscanf(fout, "%d", &x) != EOF)
//	{
//		if (x > minheap[0])
//		{
//			// 替换你进堆
//			minheap[0] = x;
//			AdjustDown(minheap, k, 0);
//		}
//	}
//
//
//	for (int i = 0; i < k; i++)
//	{
//		printf("%d ", minheap[i]);
//	}
//	printf("\n");
//
//	free(minheap);
//	fclose(fout);
//}
//
//
//void CreateNDate()
//{
//	// 造数据
//	int n = 10000;
//	srand(time(0));
//	const char* file = "data.txt";
//	FILE* fin = fopen(file, "w");
//	if (fin == NULL)
//	{
//		perror("fopen error");
//		return;
//	}
//
//	for (int i = 0; i < n; ++i)
//	{
//		int x = rand() % 1000000;
//		fprintf(fin, "%d\n", x);
//	}
//
//	fclose(fin);
//}
//
//int main()
//{
//	//CreateNDate();
//	PrintTopK("data.txt", 10);
//}