【数据结构】——二叉树堆的实现

大佬们点点关注，点点赞？！

前言

在上篇博客中我们已经介绍了树和二叉树的相关概念，相信大家都已经清楚了树和二叉树的基本思想，下面我们就来着重看看二叉树堆的实现。

在看堆的实现，我们先看看二叉树的顺序存储

一二叉树的顺序存储

二叉树的顺序存储就是以顺序表来实现的，也就是把二叉树装进数组中去实现，其中坐标代表着各个结点的位置，这里我们用到一个二叉树的性质，也就是上篇博客的性质4。如果我们存的二叉树的的结构不是完全二叉树或者是满二叉树，那么就会有空间的浪费。

那就会有人问了，为啥空的地方不存储呢，这也是我们的性质4的原因，因为我们在存的时候，需要找的孩子结点，或者父亲结点，他们的下标很重要

比如知道父亲坐标找孩子：leftchild=parent*2+1，rightchild=parent*2+2;

知道孩子坐标找父亲：parent=(leftchild-1)/2; 这里不需要判断是左孩子还是右孩子，因为这里是向下取整（因为int型向下取整的特点），所以得到的结果都是一样的。

所以如果用顺序存储最好是完全二叉树比较好，这样避免了空间的浪费，在操作中用数组存储的也就只有完全二叉树，这也从而让堆实现起来！

二堆的概念

这里的堆和操作系统里面的堆是两个东西，一个是数据结构，一个是管理系统的一块分区，这里要区分开来

现在有一段数据，然后我们把这些数据按完全二叉树的形式存储到我们的数组中，如果这组数组拆分成二叉树，符合父亲结点大于孩子结点的我们称之为大堆，反之称为小堆。

三堆的性质

1.堆的某个结点值总是不大于或者不小于其父亲结点的

2.堆总是完全二叉树

3.堆中的结点如果没有左孩子，那么肯定没有右孩子

4.堆不一定有序

四堆的实现

4.1 结构体的创建

首先堆是用顺序结构实现的，所以我们用的结构也就是和顺序表的形式是一样的

typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType * a;
	int size;//当前大小
	int capacity;//容量
}Heap;//这里和顺序表一样

4.2 堆的初始化和销毁

这里的初始化也可以直接给空间，看个人的喜好

void HeapIint(Heap* hp)
{
	assert(hp);//断言，因为hp不可能为空
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

4.3 堆的插入

堆的插入，也就是在最后面插入一个数据，这个数据插入以后，这个堆就不是堆了，因为如果是小堆，我们插入的数据比根节点还小，那么这就不符合堆的性质，所以我们需要向上调整这个算法

向上调整的算法思路就是把这个插入的数据和他这条路径上的所有数进行比较，如果小那么就交换，最终把破坏的结构恢复过来，也就是8，16，12这条路径，其他的没影响

向上调整需要用到父亲结点，也就是我们插入的是孩子，所以我们需要用孩子的坐标算出父亲的坐标

void HeapPush(Heap* hp, HeapDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)//开辟空间
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;//
		HeapDataType* tmp = (HeapDataType*)realloc(hp->a, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc fail");
			return;
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;//放入数据
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);//向上调整
                                  //这里的参数一个是数组，一个是插入数据的坐标
}

4.4 向上调整算法

void AdjustUp(HeapDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)//当孩子在第一个位置的时候也就没必要比较了所以是>0
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);//交换函数，进行交换
			child = parent;//换位置，继续比较
			parent = (child - 1) / 2;
		}
		else
		{
			break;//如果符合堆的性质，那么不玩了，直接退出来就行
		}
	}
}

这里while的条件判断可能有的人会用parent>=0去比较，这虽然可以，但是纯属巧合，具有风险，这里还是推荐使用上面的条件判断

这里函数的参数没用传堆的结构，只是传了一个数组的结构，这是因为这个的算法应用面比较广，所以不能限制死了

4.5 交换函数

void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

4.6 堆的删除

这里堆的删除如果是删最后一个元素那么就会变的毫无价值，所以我们删除第一个元素！！

如果我们删除第一个元素，那么我们的堆也就被破坏了，有两种方法，第一种也就是挪动覆盖，和数组一样，但是这样第二个元素就变成了根结点，那么他的兄弟就变成了他的儿子？！然后我们再重新建堆，因为他们的关系全乱了，所以只能这样，建堆也就是上面的操作想想都复杂。

假如之前的堆是这样的，那么调整挪动后就变成这样了

很明显这已经是发生了很大的改变。

第二种方法就是向下调整，也就是不删除第一个元素，先把他和最后一个元素交换，把最后一个元素删除，然后再让第一个元素向下调整比较，比他小的就交换（因为是小堆），最后形成的结构还是小堆，同时也成功把第一个元素删除了


void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], hp->a[hp->size - 1]);//交换，然后删除最后一个元素
	hp->size--;
	AdjustDown(a, hp->size, 0);
}

4.7 向下调整算法

这里的我们得到的是父亲结点，需要算出孩子结点，所以我们传参的时候传父亲的下标，同时由于在比较过程中需要有一个跳出循环的条件，所以我们需要把n传进去

void AdjustDown(HeapDataType* a, int n, int parent)
{
	int child = parent*2+1;
	while (child<n)//如果孩子都大于等于n了，说明比较已经到最后了，也没必要比了，再比就越界了
	{
		if (child + 1 < n && a[child + 1] < a[child])//这里需要算出哪个孩子比较小（小堆）
                                                     //child+1就是右孩子
                                                     //同时右孩子可能不存在，所以要有前面的判断条件
		{
			child++;
		}
		if (a[child] < a[parent])//下面的就和向上调整的算法差不多了
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent*2+1;
		}
		else
		{
			break;
		}
	}
}

有了上面的操作，那么下面的操作也就变得比较简单了

4.8 取堆顶元素

HeapDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}

4.9 堆的数据判空

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

4.10 堆的测试

int main()
{
	Heap hp;
	HeapIint(&hp);
	int a[] = { 12 ,15, 16, 30, 45, 25, 8 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&hp, a[i]);//把数据一个个插入进去，最终形成堆
	}
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);//取出第一个元素
		cout << top << " ";//打印
		HeapPop(&hp);//然后删除第一个元素，但是后面还是保持堆，因为采取了向下调整去维护
	}
	HeapDestory(&hp);
	return 0;
}

打印结果： 8 12 15 16 25 30 45

但是我们的本意是堆排序，并不是把这堆数据打印出来，所以我们可以这样

int main()
{
	Heap hp;
	HeapIint(&hp);
	int a[] = { 12 ,15, 16, 30, 45, 25, 8 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(&hp, a[i]);
	}
	int i = 0;
	while (!HeapEmpty(&hp))
	{
		a[i++] = HeapTop(&hp);//把取出来的数据放进数组里面去
		HeapPop(&hp);
	}
	HeapDestory(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}

但是我们又会发现这样是不是太麻烦了每次都要建一个堆，才能排序

那我们就有了下面的方法

五堆排序

5.1 向上调整建堆

假设给定一个数组，那么我们从第二个元素开始，依次去比较，比如先给第一个元素，那么这肯定是个堆。然后给第二个元素，和第一个元素比较，比较完以后，那么这个还是一个堆，然后依次放入元素，最后就形成了堆，并且还是在数组里面的

	for (int i = 1; i < n; i++)//第一个元素不用比较，所以从第二个元素开始
		{
			AdjustUp(a, i);
		}

5.2 向下调整建堆

向下调整建堆我们需要从最后一个父亲结点开始，因为最后的元素肯定都是叶结点，开始的时候他们不用去比较。比较完以后，那么当前的子树就是一个堆，那么继续往向上一个结点去向下调整，最后只剩根结点，然后进行一次向下调整即可

for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从最后一个父亲结点开始
	{
		AdjustDown(a, n, i);
	}

可能图画的比较抽象，但是画的没错！

既然有两种方法那可能有一个快一个慢，这里可以直接得出向下调整比较快时间复杂度为O(N),向上调整是N*O(logN);至于具体的解释这里就不说明了，自己也可以感觉一下，假如叶子结点有N个，那么向上调整会比向下调整的要多

5.3 排序

建完堆以后我们就要开始排序了，排序用向下调整算法，因为向下调整可以选出最大的和最小的数，因为他可以跟他的左右孩子比较，向上调整就不具备这样的优势

	for (int i = (n - 1 - 1) / 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是一直在变动的，因为排好的元素不需要进行比较了
		end--;
	}
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
}

如果是升序：建大堆

如果是降序：建小堆

因为后面的排序会把第一个元素放到后面，所以排完以后，就会变成有序的序列

5.3 topK问题

如果我们要求从一个数组中选出前k个最大的数或者最小的数，那么我们的思路是直接建立一个大堆然后依次pop9次就行，因为最后一个不用pop，直接拿出来就行，每次pop,都是最大的数所以能够完成，虽然这行得通，但是如果是几亿的数，这种方法也会很慢

所以有了下面的改进

我们可以先建立一个k个数的小堆，然后与后面N-k个元素进行比较，不满足就替换堆顶元素，然后先下调整，这里调整的范围是K，不是N,所有比较大的数会在这个小堆的底部，最后形成一个k个数最大的小堆

	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, k, i);//建小堆
	}
	for (int i = k; i < n; i++)
	{
		if (a[i] > a[0])//选出k个最大的数
		{
			a[0] = a[i];
			AdjustDown(a, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
		cout << a[i] << " ";
}

以上便是堆排序的全内容希望大家喜欢，都看到这里了