【数据结构】堆（Heap）详解----定义堆、初始化，删除、插入、销毁、判空、取堆顶

提示：以下是本篇文章正文内容

一、堆的概念及其性质：

堆的概念：

堆：是一种特殊的完全二叉树，使用数组进行存储，其所有的父结点大于等于或者小于等于它们的子结点，所以堆分为大根堆和小根堆。
大根堆（最大堆）：：所有的父结点大于等于它们的子结点，堆顶是最大值。
小根堆（最小堆）：：所有的父结点小于等于它们的子结点，堆顶是最小值。
举例：

堆的性质：

对于具有n个结点的完全二叉树，若按照从上至下，丛左至右的数组顺序对所有结点从0开始编号，则对于序号为i的节点：
1.若i=0，i为根节点编号，无双亲结点。
2.若i>0，i位置结点的双亲序号：（i-1)/2；
3.若2i+1<n，左孩子序号：2i+1。
4.若21+2<n，右孩子序号：2i+2。

二、堆的定义及其基础操作的代码实现（C语言版）

因为堆的定义以及销毁、初始化很简单，就不赘述啦，直接看代码。难点主要在于堆的插入和删除，我们会用到两种方法向上调整法和向下调整法，我会详细讲述。

1.定义堆

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _arr;
	int _size;//有效数据个数
	int _capacity;//空间大小
}Heap;

2.堆的初始化

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->_arr = NULL;
	hp->_capacity = hp->_size = 0;
}

3.堆的销毁

void HeapDestory(Heap* hp)
{
	assert(hp);
	if(hp->_arr) free(hp->_arr);
	hp->_arr = NULL;
	hp->_capacity = hp->_size = 0;
}

4.堆的插入

对于堆的插入我们可以分两种情况：
1.插入的结点是根结点，那么就直接hp->_arr[hp->_size] = x就行。
2.若插入的不是根节点，那么我们不仅要hp->_arr[hp->_size] = x，还需要进行向上调整。
向上调整法（以小根堆为例，掌握啦小根堆大根堆也就会啦~）：
其思想主要是将元素直接插入到最后一个位置，若不是根结点，则需要与其父结点进行比较，若比父结点小，则与父节点进行交换，一直重复该操作，直到孩子结点大于等于父结点或者到根结点。
为了方便柚柚们理解，我来为柚柚们讲一个例子：

以6 5 4 3为例：
第一次插入6的时候，为根节点，此时直接插入作为根结点，不需要调整，_size++。

第二次插入5的时候，此时5有父结点，其父节点序号为(1-1)/2 = 0，即为6，发现孩子结点比父结点小，我们就要把它们交换，交换之后让孩子结点指向序号为0的结点，此时为根节点不需要调整，插入完成，_size++。

第三次插入4，此时4有父结点，其父节点序号为(2-1)/2 = 0，即为5，发现孩子结点比父结点小，所以我们要把它们交换，交换之后让孩子结点指向序号为0的结点，此时为根节点不需要调整，插入完成，_size++。

第四次插入3，此时3有父结点，其父节点为(3-1)/2 = 1，即为6，发现孩子结点比父结点小，所以我们要把它们交换，交换之后让孩子结点指向序号为1的结点，然后再让1这个位置的结点与其父结点比较，其父结点为(1-1)/2 = 0,即为4，发现孩子结点比父结点大，我们就不需要再进行调整，插入完成，_size++。

整个过程就是这样，其实是很好理解，看完图应该就能够理解啦~

代码实现：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上调整法
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;

	while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
	{
		if (arr[child] < arr[parent])//若孩子结点比父结点小则交换
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);

	if (hp->_capacity == hp->_size)
	{
		int newCapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;//分配空间，因为刚开始容量为0，所以要特殊处理
		HPDataType* tmp = (HPDataType*)realloc(hp->_arr,newCapacity * sizeof(HPDataType));
		if (tmp == NULL)  exit(1);//分配内存失败，结束程序
		hp->_arr = tmp;
		hp->_capacity = newCapacity;
	}
	hp->_arr[hp->_size] = x;

	AdjustUp(hp->_arr, hp->_size);//向上调整法
	
	hp->_size++;
}

5.堆的删除

对于堆的删除我们需要注意的是我们删除的是根结点，为了方便删除根节点，我们将根结点与最后一个结点进行交换，然后_size–，就把根节点删啦，但是此时打乱了堆的顺序，根结点可能就不是最小的啦，所以我们要对根节点进行向下调整。具体步骤就是，让交换之后的根结点与它的孩子结点比较，若比孩子结点大，则与孩子结点交换，然后让父节点指向该孩子结点，直到孩子结点的下标大于等于n(结点的个数）或者比其孩子结点都小；若比孩子结点们小，则结束，删除完成，其实理解了向上调整，向下调整就很容易理解啦，所以我就不再举例子啦。

//向下调整法
void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子

	while (child < n)
	{
		//找左右孩子中找最小的
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;

		}
		else
		{
			break;
		}
	}
}

void HeapPop(Heap* php)
{
	assert(php && php->_size);

	Swap(&php->_arr[0], &php->_arr[php->_size - 1]);

	--php->_size;

	AdjustDown(php->_arr, 0, php->_size);
}

6.取堆顶的数据

HPDataType HeapTop(Heap* php)
{
	assert(php && php->_size);

	return php->_arr[0];
}

7.堆的数据个数

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

8.堆的判空

bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->_size == 0;
}

总结：

若是还没有理解向上调整法和向下调整法，柚柚们可以多看看代码多画画图，还有就是自己搞几个样例跟着程序调试，就可以搞懂啦~，日后还会更新堆排还有其它数据结构的知识，感兴趣的柚柚们可以三连，关注博主喔！