数据结构（四）————二叉树和堆（中）

制作不易，三连支持一下呗！！！

文章目录

前言
一、堆的概念及结构
二、堆的实现
三.堆的应用

总结

前言

CSDN

这篇博客介绍了二叉树中的基本概念和存储结构，接下来我们将运用这些结构来实现二叉树

一、堆的概念及结构

1.概念：

堆是一种完全二叉树，但是堆中每个节点都不大于（或不小于）其父节点，这样的完全二叉树就称为堆。

堆的性质：堆中每个节点都值都不大于（不小于）其父节点的值

堆是一种完全二叉树

堆分为大堆和小堆：根节点为最大值的是大堆，根节点为最小值的是小堆。

2.结构：

堆通常采用的是顺序存储的方式，即将数据存储在数组中，通过父节点和孩子节点下标的关系来相连起来。

typedef int HPDateType;

typedef struct Heap
{
	HPDateType* a;
	int size;
	int capacity;
}HP;

二.堆的实现

1.堆的初始化和销毁

这个部分比较简单，直接放代码

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

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

2.堆的插入数据（向上调整算法）

每次插入数据后我们都需要调整数据的位置，以保证满足堆的定义，这里我们写了一个向上调整函数

//向上调整算法
void AdjustUp(HPDateType* a,int child)
{
	int parent = (child - 1) / 2;

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

这里我们建的是小堆，所以判断条件是孩子的值小于父亲的值时就交换。

所以 push数据时，在插入到size位置的基础上，只需要加一个向上调整函数的调用即可。

void HPPush(HP* php, HPDateType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacitty = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDateType* tmp = (HPDateType*)realloc(php->a, sizeof(HPDateType)*newcapacitty);
		if (tmp == NULL)
		{
			perror("realloc:");
			return;
		}
		php->capacity = newcapacitty;
		php->a = tmp;
	}

	php->a[php->size] = x;
	php->size++;

	//向上调整
	AdjustUp(php->a,php->size-1);
}

下面我们分析一下向上调整算法建堆的时间复杂度：

	//建堆
    int i = 0;
	for(i = 0; i <10; i++)
	{
		HPPush(&hp, a[i]);
	}

假设我们要N个节点，树的深度是h。

这样我们就可以得到 $2^{h-1}$ <N<= $2^{h}-1$

反解得 $\log (N+1)$ <h< $(\log N)+1$ ，近似可得h约等于logN。

因为向上调整最坏情况下会调整高度次，而高度约等于logN，所以向上调整算法的时间复杂度就是logN。

void HPInitArray(HP* php, HPDateType* a, int n)
{
	assert(php);
	php->a = (HPDateType*)malloc(sizeof(HPDateType)*n);
	if (php->a == NULL)
	{
		perror("Init:");
		return;
	}

	memcpy(php->a, a, n * sizeof(HPDateType));
	php->capacity = php->size = n;
	//建堆
	for (int i=1; i < php->size; i++)
	{
		AdjustUp(php->a, i);
	}
}

那么用向上调整算法建堆时，在插入第k层的数据时，最多向上调整k-1次，第k层有 $2^{k-1}$ 个节点，这些节点共需向上调整（k-1）* $2^{k-1}$ 次。

所以时间复杂度o（N）=1* $2^{1}$ +…+（h-1）* $2^{h-1}$ = $2^{h}*$ （h-2）+2

又因为h约等于logN

o（N）=N*（ $\log$ N-2）+2。近似为N*logN

3. 删除数据（向下调整算法）

注意：堆删除数据时是删除堆顶的数据，而不是最后一个位置的数据！！！

可能大家首先想到的删除方法是挪动数据向前一个覆盖。

但是这种方法有两个缺陷：

1.这种操作的时间复杂度是o（N），效率不是很高。

2.这种操作完全破坏了之前建立的堆的结构，最后我们还要耗费大量的操作时间来重新建堆。

因此，这里我们采用另一种思路：

先交换最后一个位置和堆顶元素，再size--。这样我们就删除了堆顶数据，并且并没有完全破坏掉堆的结构，因为除堆顶数据外，堆顶元素的左子树和右子树依旧还是堆结构，我们只需要将堆顶元素向下调整，将它放置在合理位置就可以了。

向下调整算法：

//向下调整算法
void AdjustDown(HPDateType* 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 = child * 2 + 1;
		}
		else {
			break;
		}
	}
}

注意：我们依旧以小堆为例，在调整时我们的思路是：和孩子中小的那个值比较，如果孩子比父亲的值要小，就交换，并更新孩子和父亲的值，循环操作，直到终端结点。

向下调整算法的适用条件：下面的节点是堆。

那么我们pop操作就比较简单了。

pop函数：

//删除堆顶数据
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	//向下调整
	AdjustDown(php->a, php->size, 0);
}

我们接着分析一下使用向下调整算法建堆的时间复杂度：

为满足向下调整算法的条件，我们从最后一个节点的父节点开始向下调整。

void HPInitArray(HP* php, HPDateType* a, int n)
{
	assert(php);
	php->a = (HPDateType*)malloc(sizeof(HPDateType)*n);
	if (php->a == NULL)
	{
		perror("Init:");
		return;
	}

	memcpy(php->a, a, n * sizeof(HPDateType));
	php->capacity = php->size = n;

	//向下调整建堆
	for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

同向上调整算法类似，时间复杂度O(N)=1* $2^{h-2}$ +…+(h-1)* $2^{0}$ = $2^{h}$ -1-h.

由满二叉树h=log（N+1）得O（N）=N-log（N+1）

所以使用向下调整算法建堆的时间复杂度为O（N）=N。

比使用向上调整建堆效率提高了非常多！！！

4.其他一些小函数

//取堆顶数据
HPDateType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

//判断堆是否为空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

这两个函数非常简单，有之前顺序表，链表，栈和队列的基础，应该是不难理解的。

三.堆的应用（堆排序和TopK问题）

1.TopK问题

TopK问题：即求数据结合中前K个最大的元素或最小的元素，一般情况下数据量都比较大。

比如我们要从100亿个数据中找到最大的前十个数是多少。

我们没有了解堆之前可能想法就是：将数据存到一个数组中，用排序算法排序一下，最后取最大的十个数。

但是这样的方法实践中是不可行而且就算可行效率也不高的。

但是根据堆的性质，堆顶的元素就是最大值或最小值。那如果我们要找最大的十个数，我们就建小堆，初始先将所以数据中的前十个元素建成一个小堆，依次遍历数据，如果数据比堆顶元素大就将堆顶元素替换成这个数据，并向下调整，保持小堆的状态。直至结束，最后在小堆中的十个值就是最大的十个数。

时间复杂度O（N）=K+（N-K）*logK。

这里我们采用循环产生随机数的方法来创造大量随机数据来模拟TopK问题。

这样我们就创造了有10000个数据的文件，并且这些数据的大小都在1000000以内。

这时我们手动在10个数据后面补位使它们大小超过1000000，那么如果程序正确，我们最后打印出来的值是10个比1000000大的值。

结果和预期相同，证明我们都程序大概率是没什么问题的。

2.堆排序

如果我们想要将一组数排成升序，我们就建大堆，要排成降序，就排成小堆

void HeapSort(int* a, int n)
{
	//建堆
	for (int i = (n - 1 - n) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

堆排序的时间复杂度计算时和向上调整建堆一样，都是N*logN，我们忽略最开始建堆（O（N））的消耗。