你真的会数据结构吗：堆

❀❀❀ 文章由@不准备秃的大伟原创 ❀❀❀

♪♪♪ 若有转载，请联系博主哦~ ♪♪♪

❤❤❤ 致力学好编程的宝藏博主，代码兴国！❤❤❤

好久不见，甚是想念，不知道大家有没有察觉到大伟的头像和名字变了鸭 <(*￣▽￣*)/ ，哈哈，大伟现在是伟大啦，哈哈！

前一周大伟雀食是很忙啊，课很多，但是这周也算是忙里偷闲了，久违的来更一更博客，哎呀，不过太久没来碰博客，大伟都不清楚自己写到哪里了，大家为何不帮我看看上一期的内容呢？ ○( ＾皿＾)っHiahiahia… ------->队列

哦哦，没错，我们上次学到队列了，嘿嘿，那我们就继续数据结构的学习：树。

那这时候就有人好奇了，这个树是个啥啊，这树长得千奇百怪的，有啥规律啊？诶，别急嘛，那学习树之前，我们还得来了解一下树是什么类型的结构：

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

长啥样？上图！

不知道有没有眼睛好的同学发现，上面这棵树上的是不是有些很标致啊？没错，这棵树的每个节点（还是说树枝）都是左右分叉的，那这个图片里的树和我们的数据结构的数有什么关联呢？诶，这关联可大了，简单说，把这个照片反过来就是我们的数，还是最经典的二叉树哦~

哈哈，这么说大家可能还是不理解，那来看看我们数据结构里面树的逻辑结构图吧：

相信凭大家的水平，不需要大伟多说也能理解了吧，好，本篇博客到此为止，谢谢大家观看~

——————————————————————————————————————————

嘿嘿~ 简单说一下树的各种定义吧：

最上面的节点，称作根节点（树根）
节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为2
叶节点或终端节点：度为0的节点称为叶节点；如上图：H、I、J、F..等节点为叶节点非终端节点或分支节点：度不为0的节点；如上图：D、E、B、C...等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为2
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：D、F互为堂兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

此外，大伟还要多嘴一句，子树之间不能有交集，因为那样的话就成为了 “图” ，这也是我们后面要学的，不过现在可以不用管。

那接下来我们开始实现一下树吧，那实现什么样子的树呢？就上面图片里面的那样就可以咯，那我们还给这种特殊的数起了个专门的名字： 二叉树，是不是听名字就能想到样子呢，哈哈。

万事开头难，我们要用什么方法实现二叉树呢？其实这个问题前人也想了很多方法，不过最后我们选用的也是现在最流行的一种方法，我们称之为：孩子兄弟表示法

那何为孩子兄弟表示法呢？简单来说，就是上面的定义（嘿嘿( >ρ < ”)）

树，我们要实现什么功能呢？一个结构不仅要好看，也需要有用，那我们树有什么用呢？

其实我知道的，大家应该都有好奇的地方，大伟的标题写的是堆，但是前面的内容都是介绍的数，是不是大伟学傻了，糊涂了？当然不是，哈哈，那还得了。其实我们数的实现就是以堆为基础的，简单说，树就是在堆的基础之上搭建的，所以我们这一篇要实现的内容是：堆！

那堆的性质有啥呢？

一.堆中某个节点的值总是不大于或不小于其父节点的值；

二.堆总是一棵完全二叉树。

根据性质一，我们还可以把堆分为大堆和小堆，那大堆和小堆分别是什么意思呢？

大堆：在二叉树的逻辑结构下，上面一层总是比下面一层的数据（父亲总是比子女）大

小堆：在二叉树的逻辑结构下，上面一层总是比下面一层的数据（父亲总是比子女）小

上逻辑图（以小堆为例子）：

如上图，那堆的逻辑结构是啥样的？和二叉树一个样，那物理结构呢？数组。

好，那我们要实现什么接口呢？

首先是堆的创建，没话说，然后就是需要把当前的堆的物理结构打印出来，此外，既然我们都分了大小堆，于是我们就需要实现大小堆的接口，此外，如果没有数据也无法成堆，于是我们需要有一个插入的接口，光增不删也不行是吧，于是就来一个删除，然后就是取堆顶（根），堆判空，堆的数据个数，销毁堆。暂时也就这些接口了，好，开码！

Heap.h

结构体：需要一个数组，一个堆的最大容量，堆的目前容量（和顺序表一样的定义）

typedef int HpDataType;
typedef struct Heap
{
	int* a;
	int sz;
	int capacity;
}Heap;

接着就是接口的声明：

// 堆的构建
void HeapCreate(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HpDataType x);
//向上调整
void AdjustUp(HpDataType* a, int child);
//向下调整
void AdjustDown(HpDataType* a,int n, int child);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HpDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);

Heap.c

堆的创建：

void HeapCreate(Heap* hp)
{
	assert(hp);

	hp->a = NULL;
	hp->capacity = hp->sz = 0;
}

堆的销毁：

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

向上调整：

可能会有铁汁好奇，这个向上调整是什么，还记得孩子兄弟法吗，就是当我们插入一个数据（尾部）的时候，我们不知道这个数据的大小，比如小堆的时候，若我们插入的数据比较小，需要进入到中间的某个位置，那我们这个时候就需要向上调整，当然了，逻辑结构上就是这个数依次网上交换数据，直到到合适的位置上，也就是说满足小堆的定义。

那物理结构上怎么看呢？其实也不难，就是一个数组的下这边搞搞，那边搞搞。具体咋搞捏，如下：

就比如这个，如果我们想把16（下标为6）的数调到他的父亲节点去，怎么办，诶，根据逻辑结构：

我们（6-1）/ 2 == 2 （整形），如果是吧81和15交换呢？（5-1）/ 2 == 2，还是可以得到父亲节点的坐标，其他的子树类推，这样就好搞了，如果孩子要往上调，就直接减一再除二，代码如下：

void AdjustUp(HpDataType* 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;
		}
	}
}

当然了，向下调整里面调用了交换函数，相信大家已经如张飞吃豆芽，小菜一碟了吧，

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

好，给兄弟们出个问题：上面的交换函数写的对不对？

没问题啊，是吧？那我再问一句，出了Swap函数后，两个数的值真的交换了吗？

这边就是考基础知识了，我们在函数内部交换了数据，但是呢，一出函数，栈帧销毁了，我们的值还是没有变化，一切都白费了，那咋解决？传地址呗，别忘了，C语言的灵魂，指针！于是我们就可以这么写：

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

插入数据：

void HeapPush(Heap* hp, HpDataType x)
{
	assert(hp);
//如果堆为空或者满了
	if (hp->capacity == hp->sz)
	{
		int newcapacity = hp->capacity == 0 ? 4 : 2 * (hp->capacity);
		HpDataType* tmp = realloc(hp->a, newcapacity * sizeof(int));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		hp->a = tmp;
		hp->capacity = newcapacity;
	}

	hp->a[hp->sz] = x;
	hp->sz++;
//向上调整，记住是下标，所以sz要-1
	AdjustUp(hp->a, hp->sz-1);
}

那啥时候需要向上调整啊？仔细想想，我们插入数据是向下调整，那么删除数据不就是向上调整了吗？没错，那我们如何删数据呢？有很多办法，但是大伟也只讲其中的一种，先说一下思想：

将堆顶（根）和最后一个节点交换，此时直接size--，这个时候的堆顶（根）是之前的比较大的值，然后我们将根依次向下调整，直到位于合适的位置，此时还是个小堆。

那么物理结构呢？其实和向上调整很像，不同的就是父子节点交换，简单看一下逻辑结构：

还是这张图，如果我们要把15（下标为2）的值调到81（位置为5）该怎么调，直接2*2+1就可以了，但是如果我们将这两个值交换后，出现了新的问题：此刻的下标为2位置的值比下标为6位置的值要大，这样就不是小堆了，于是，向下调整在调整前还需要一些判断。如果左孩子大于右孩子，我们就让孩子加一，让父亲与右孩子交换，但是，其中有一个小细节，我们的堆不一定是完全二叉树，也就是我们不一定有右孩子，所以，还需要判断右孩子存在，代码如下：

向下调整：

void AdjustDown(HpDataType *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 HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));

//根据思想，首尾交换
	Swap(&hp->a[0], &hp->a[hp->sz - 1]);
	hp->sz--;

//第二个传的是n，所以不需要-1！
	AdjustDown(hp->a,hp->sz, 0);

}

返回堆的大小：

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->sz;
}

返回堆顶元素：

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

堆判空：

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

这样，我们的小堆就基本实现完成了，简单写一个案例，赶紧来试试吧！

test.c

int main()
{

	int a[] = { 60,70,65,50,32,100 };

	Heap hp;
	HeapCreate(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
//入堆
		HeapPush(&hp, a[i]);
	}

	printf("%d\n", HeapTop(&hp));//32
	HeapPop(&hp);//删除32
	printf("%d\n", HeapTop(&hp));//50
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));//50 60 65 70 100
		HeapPop(&hp);
	}

	HeapDestory(&hp);
	return 0;
}

咱们来看看答案是不是和我们的预想一样呢：