数据结构——二叉树堆的专题

1.堆的概念及结构

如果有一个关键码的集合K = {K0 ，K1 ，K2 ，K3…，K(N-1) }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2*i+1且 Ki<=K2*i+2 ) i = 0，1， 2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

2.堆的性质

（1）堆中某个结点的值总是不大于或不小于其父结点的值； 

（2）堆总是一棵完全二叉树。

3.堆的实现

1.第一种
 

/*向上调整算法（此代码适合大堆）*/
void xiangshang(int *a,int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] < a[child])
		{
			int c;
			c = a[parent];
			a[parent] = a[child];
			a[child] = c;
		}
		/*else
		{
			break;
		}*/
		child = parent;
		parent = (child - 1) / 2;
	}
}
/*建堆（此代码会建成大堆）*/
void jiandui(int *b,int n)
{
	for (int i = 0; i < n; i++)
	{
		xiangshang(b, i);
	}
}

第一种建堆的具体讲解请看《四种排序方法的补充》 ，里面配有图文讲解，也有向上调整算法与向下调整算法（后面要用到）的图文讲解，希望你可以有耐心的看另一篇文章，希望我的这些讲解对你有用。

C--四种排序方法的补充-CSDN博客

2.第二种

1.创建堆所需要的模型

#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

size是确定我开辟的空间中，用掉了多少空间。capacity是确定我开辟了多少个空间。 

2.堆的初始化

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

3.堆的销毁

/*销毁*/
void Destroy(HP* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
}

这里要注意的是free（ps->a）之后，free(ps)是错误的操作。不可以销毁ps 

4.插入

/*插入（通过插入会形成大堆）*/
void HeapPush(HP* ps, HPDataType x)
{
	assert(ps);
	assert(x);
	if (ps->capacity == 0)
	{

		HPDataType* b = (HPDataType*)malloc(sizeof(HPDataType) * 4);
		if (b == NULL)
		{
			perror("malloc");
			exit(0);
		}
		ps->capacity = 4;
		ps->a = b;
	}
	if (ps->size == ps->capacity)
	{
		HPDataType newcapacity = 2 * ps->capacity;
		HPDataType* b = (HPDataType*)realloc(ps->a, newcapacity * sizeof(HPDataType));
		if (b == NULL)
		{
			perror("relloc");
			exit(0);
		}
		ps->a = b;
		ps->capacity = newcapacity;
	}
	ps->a[ps->size] = x;
	ps->size++;
	xiangshang(ps->a, ps->size - 1);
}

在插入之前我要先判断我是否开辟了空间，然后判断这个空间是否已经被填满。最后再将你所需要的数字放入到最后的位置，通过向上调整算法完成排序。 

5.删除元素

/*向下调整算法（此代码适合大堆）*/
void xiangxia(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])
		{
			int c;
			c = a[child];
			a[child] = a[parent];
			a[parent] = c;
		}
		parent = child;
		child = parent * 2 + 1;
	}
}
/*删除元素（此代码在删除元素后还是会形成大堆）*/
void HeapPop(HP* ps)
{
	assert(ps);
	assert(ps->size > 0);
	HPDataType b = ps->a[0];
	ps->a[0] = ps->a[ps->size - 1];
	ps->a[ps->size - 1] = b;
	ps->size--;
	xiangxia(ps->a, ps->size, 0);
}

删除元素删除的是根的元素，所以我先将根元素与最后的一个元素进行调换位置，然后让size--，（size--是因为下一次插入时，会将那个元素覆盖掉。）最后通过向下调整对这个堆重新排序，（注意：这个代码的前提是这个堆是大堆）让第二个大的坐到根的位置。

6.返还树根元素

/*返回树根元素*/
HPDataType HeapTop(HP* ps)
{
	assert(ps);
	assert(ps->size > 0);
	return ps->a[0];
}

7.判断是否为空

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

因为当我初始化之后，size便是0，只有当插入元素之后，size才会大于或等于1。 

8.算多少个

/*算多少个数*/
int HeapSize(HP* ps)
{
	assert(ps);
	return ps->size;
}

9.打印树的内容

/*打印树的内容*/
void HeapPrintf(HP* ps,int size)
{
	int i = 0;
	for (; i < size; i++)
	{
		printf("%d ", ps->a[i]);
	}
}