深入理解数据结构第一弹——二叉树（1）——堆

前言：

准备工作：本人习惯将文件放在test.c、SeqList.c、SeqList.h三个文件中来实现，其中test.c用来放主函数，SeqList.c用来放调用的函数，SeqList.h用来放头文件和函数声明

一、什么是树

如图，其中0所在位置被称为树顶或者树根都可以，下面的称为子树，其中1所在分叉称为左子树，2所在分叉成为右子树

还有一些规则如下：

对于学过离散数学的同学来说这部分知识并不难，没有学过的自己再去搜一下了解一下吧，这里只讲了一些大概内容

二、什么是堆

树里面有几个特殊的概念，例如完全二叉树和满二叉树，而堆就是完全二叉树的一种，完全二叉树就是除了最后一层外，其他层节点数达到最大

堆与普通的完全二叉树的不同在于它的大小堆的性质

例如：

三、堆的节点结构

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int sz;
	int capacity;
}HP;

四、堆的基本操作

//初始化
void HeapInit(HP* php);
//销毁
void HeapDestory(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//找堆顶元素
HPDataType HeapTop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//算个数
int HeapSize(HP* php);

看上面的函数声明部分我们就可以看到我们每一步要实现的内容，接下来，我们就来一步一步进行实现

1、初始化

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

2、销毁

//销毁
void HeapDestory(HP* php)
{
	free(php->a);
	free(php);
}

3、插入元素

//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//删除

//向上调整(小堆)
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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整
void AdjustDown(int* 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 HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->sz == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->sz] = x;
	php->sz++;

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

4、判断栈顶元素是否为空

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

5、删除元素

//删除
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->sz - 1]);
	php->sz--;
	//向下调整
	AdjustDown(php->a, php->sz,0);
}

6、返回树根元素

//找堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}

7、算个数

//算个数
int HeapSize(HP* php)
{
	assert(php);
	return php->sz;
}

五、完整代码实例

SeqList.h

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int sz;
	int capacity;
}HP;

//初始化
void HeapInit(HP* php);
//销毁
void HeapDestory(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//找堆顶元素
HPDataType HeapTop(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//算个数
int HeapSize(HP* php);

test.c

//堆
int main()
{
	HP hp;
	HeapInit(&hp);
	int a[] = { 65,100,70,32,50,60 };
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d ", top);
		HeapPop(&hp);
	}
	return 0;
}

SeqList.c

//堆
//初始化
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->sz = 0;
}
//销毁
void HeapDestory(HP* php)
{
	free(php->a);
	free(php);
}
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//删除

//向上调整(小堆)
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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整
void AdjustDown(int* 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 HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->sz == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->sz] = x;
	php->sz++;

	//向上调整
	AdjustUp(php->a, php->sz - 1);
}
//删除
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->sz - 1]);
	php->sz--;
	//向下调整
	AdjustDown(php->a, php->sz,0);
}
//判断是否为空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->sz == 0;
}
//找堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}
//算个数
int HeapSize(HP* php)
{
	assert(php);
	return php->sz;
}