【数据结构：堆】——堆及堆的相关操作（C语言）

1、什么是堆？

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

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一个完全二叉树；
  
  注意：这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
  详细了解：堆的详解

2、堆的实现

实现思路：堆只是逻辑上的一种数据结构，而事实堆物理上还是数组。所以我们都要把对堆逻辑上的操作转化为对数组物理上的操作。
所以我们在建堆的时候就是在数组上面进行操作调整，将严格物理上的数组调整成逻辑上的大堆/小堆。这就产生了堆的向下调整算法;
堆的向下调整算法：
思路：根据大小根堆的要求进行变化，大根堆根节点必须大于左右子树节点而小根堆根节点必须小于左右子树节点，通过对父亲节点和孩子节点的比较进行交换两个值来达到要求。
向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
例如：数组int a[] = {27,15,19,18,28,34,65,49,25,37}，建成小根堆的图示。

但是大多数情况下给我们的数组看以看作是一个完全二叉树，但通过算法调整的时候它的左右子树都不是却不是堆，这种情况解决方案是：这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

依此我们就可以总结：在建堆的时候不管所给的数组是怎样出了不能看成完全二叉树的数组，我们只需要从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就一定可以调整成堆。
堆的建立：
例如：数组int a[] = {1,5,3,8,7,6}，可以看成是完全二叉树，但它的左右子树却不是堆。先求要求建成大堆，方法就是上面所总结的。

堆的插入：
思路：先将数据插入到堆中也就是数组的尾部，然后因为原先的对已经有序，所以只需要进行向上比较将新插入的数据放到合适的位置就行。这叫：向上调整算法
例如：

堆的删除：
思路：堆的删除其实就是删除堆顶元素，先将堆顶元素和队尾元素进行交换，然后在删除队尾元素，在进行一次向下调整即可（只是交换了堆顶和堆尾不影响其他），另外为什么交换因为删除堆顶元素其实就是物理上删除数组首元素，这样消耗较大（数组元素统一前移），不如首尾交换删除尾部代价小。

堆排序：
思路：其实也是选择排序的一种，重点在 **“选择”**上。不管是大根堆还是小根堆它的堆顶都是这个数组中最大或者最小的，这就是一种选择每次选择最大或者最小的元素。那如何排序呢！升序排大堆、降序排小堆。以大堆为例：每次堆顶都是当前所有元素中最大的，那么我们将堆顶和堆尾的元素进行交换，然后再将队尾下标前移将最大的那个 屏蔽然后在进行调整调整好后重复上述操作。降序同样如此！

3、代码实现

【注意】：这里不给出头文件，读者自己加上
函数接口功能声明:
Heap.h文件

typedef int HPDataType;//堆中的数据类型

typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

void Swap(HPDataType*a, HPDataType* b);//交换两个数
void HeapInit(Heap* hp, HPDataType* a, int n);
void AdjustDown(HPDataType* a, size_t n, size_t parent);//向下调整
void AdjustUp(HPDataType* a,size_t parent);//向上调整 用于向堆中插入元素时
void HeapDestory(Heap* hp);//销毁堆
void HeapPush(Heap* hp, HPDataType x);//插入一个数据进入堆
void HeapPop(Heap* hp);//删除堆中元素
HPDataType HeapTop(Heap* hp);//取到堆中元素
int Heapsize(Heap* hp);//堆中元素个数
int HeapEmpty(Heap* hp);//判断堆中是否为空
void HeapSort(int* a, int n);//堆排序
void HeapPrint(Heap* hp);//输出堆中元素

Heap.c

void Swap(HPDataType*a, HPDataType* b)//交换两个数
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

void HeapInit(Heap* hp, HPDataType* a, int n)
{
	hp->_a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	memcpy(hp->_a, a, sizeof(HPDataType)*n);
	hp->_capacity = n;
	hp->_size = n;

	//构建成堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(hp->_a, hp->_size, i);
	}
}

//二叉树左孩子leftchild = parent * 2 + 1;
//二叉树右孩子rightchild = parent * 2 + 2;

void AdjustDown(HPDataType* a, size_t n, size_t parent)//调整小/大根堆
{
	size_t 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 AdjustUp(HPDataType* a, size_t child)//向上调整
{
	assert(a);
	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 HeapDestory(Heap* hp)//销毁堆
{
	assert(hp->_a != NULL);

	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

void HeapPush(Heap* hp, HPDataType x)//插入一个数据进入堆
{
	//增容问题
	if (hp->_size == hp->_capacity)
	{
		int new_capacity = hp->_capacity == 0 ? 8 : hp->_capacity * 2;
		hp->_a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)*new_capacity);
		assert(hp->_a);
		hp->_capacity = new_capacity;
	}

	//插入数据
	hp->_a[hp->_size] = x;
	++hp->_size;

	//向上调整
	AdjustUp(hp->_a, hp->_size-1);

	
}

void HeapPrint(Heap* hp)//输出堆中元素
{
	assert(hp->_a != NULL);

	for (int i = 0; i < hp->_size; i++)
	{
		printf("%d ", hp->_a[i]);
	}
	printf("\n");

	//printf("%d\n", hp->_capacity);
	//printf("%d\n",hp->_size);

}

void HeapPop(Heap* hp)//删除堆顶元素
{
	assert(hp);

	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);//首尾交换
	hp->_size--;
	AdjustDown(hp->_a, hp->_size, 0);//向下调整

}

HPDataType HeapTop(Heap* hp)//取到堆顶元素
{
	assert(hp);

	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);//首尾交换
	HPDataType p = hp->_a[hp->_size - 1];
	hp->_size--;
	AdjustDown(hp->_a, hp->_size, 0);
	return p;
}

int Heapsize(Heap* hp)//堆中元素个数
{
	assert(hp);

	return hp->_size;//数显数组下标
}

int HeapEmpty(Heap* hp)//判断堆中是否为空
{
	assert(hp);

	if (hp->_size == 0)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

void HeapSort(int* a, int n)//堆排序
{
	int end = n - 1;
	//升序 排大堆

	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, n - 1);
	}

	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

main.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

int main()
{
	void TestHeap()
{
	Heap pl;
	int a[] = { 93, 72, 48, 53, 45, 30, 18, 36, 15, 35 };
	
	HeapInit(&pl, a, sizeof(a)/sizeof(HPDataType));
	HeapPrint(&pl);//输出堆
	HeapPush(&pl, 80);//队尾插入80
	HeapPrint(&pl);
	HeapPop(&pl);//删除堆顶元素
	HeapPrint(&pl);
	printf("%d\n",HeapTop(&pl));
	HeapPrint(&pl);
	HeapSort(a, sizeof(a) / sizeof(HPDataType));//堆排序
	//输出排序后的数组
	for (int i = 0; i < sizeof(a) / sizeof(HPDataType); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
	system("pause");
	return 0;
}

运行截图