二叉树（二）——堆的代码实现

堆用数组实现其物理结构，利用leftchild=2*parent+1以及rightchild=2*parent+2进行父子结点的访问。

堆的基本结构：
 

typedef int HPDataType;
typedef struct Heap {
	HPDataType* a;//动态数组
	size_t size;//数据量
	size_t capacity;//容量
}HP;

堆的初始化函数：

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

堆的清零函数

void HeapDesTroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;//这一步不要忽略
	php->size = php->capacity = 0;
}

堆中添加新元素时，应该：

①保持大根堆（或小根堆）的原有性质不便，即插入新元素后仍然是大根堆（或小根堆）。

②尽量不破坏原有树结构的完整性。

③采用尾插方式，不必大批量挪动数据，以提高效率。

堆中插入新元素的函数（AdjustUp为向上调整函数）：

void AdjustUp(HPDataType* a,size_t child)
{
	//父子关系计算公式（对于leftchild和rightchild均成立）
	size_t parent = (child - 1) / 2;
	//可能会持续上调
	//此处为小堆，若需要大堆，则只用调整if中的符号就行
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//更新关系
			child = parent;
			parent = (child - 1) / 2;
			//注意child=0时，parent=0,会陷入死循环。
			//无论用不用size_t，parent始终不会小于0
			//-1/2==0
		}
		//还应该考虑中间就停止的情况
		else
		{
			break;
		}
	}
}


//插入新数据后，要保持大根堆、小根堆的性质
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//空间不够，先扩容
	if (php->capacity == php->size)
	{
		size_t newCapacity = php->capacity * 2 + 1;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed.\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	//堆中插入数据——向上调整算法
	//第一步：先把新数据放在物理结构（顺序表/数组）的尾部
	php->a[php->size] = x;
	++php->size;
	//第二步：向上调整
	AdjustUp(php->a, php->size - 1);
}

删除根的函数

void AdjustDown(HPDataType* a,size_t size,size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		//第一步：选出左右孩子中较小的一个
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		//如果孩子小于父亲则交换，并继续往下调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//删除堆顶数据（小堆-删除堆顶最小数据/大堆-删除堆顶的最大数据）
//要保持小堆/大堆的性质
//若直接前移剩余数据，则有问题：①破坏结构②时间复杂度为O（N）,不方便
//更优秀的方案：第一个数据先和最后一个数据进行对调->不必抹掉数据，直接size--即可->向下调整
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//第一步：根与最后一个数据进行交换
	Swap(&php->a[0], &php->a[php->size-1]);
	//第二步：删除数据
	--php->size;
	//第三步：向下调整
	//时间复杂度：O(logN)
	AdjustDown(php->a,php->size,0);
}

堆排序函数

//堆排序的步骤比较简单，即：
//将数组中的无序元素全部放到一个新建的堆中，再依次pop出，即得有序的元素列
//堆排序——升序
void HeapSort(HPDataType* a, int size)
{
	//第一步：建立一个堆（小堆）
	HP hp;
	HeapInit(&hp);
	//第二步：将数组中的无序数据都放到堆中
	//第三步：由于小堆可以依次弹出从小到大的数据，故依次放入数组即可
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);
	}
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDesTroy(&hp);
}

完整代码（含测试用例）

Heap.h

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap {
	HPDataType* a;//动态数组
	size_t size;//数据量
	size_t capacity;//容量
}HP;
void Swap(HPDataType* pa, HPDataType* pb);
void HeapInit(HP* php);
void HeapDesTroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
void HeapPrint(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);

Heap.c

#include"Heap.h"
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void HeapDesTroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;//这一步不要忽略
	php->size = php->capacity = 0;
}

void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

//算法逻辑思想是二叉树，物理上操作的是数组中数据
void AdjustUp(HPDataType* a,size_t child)
{
	//父子关系计算公式（对于leftchild和rightchild均成立）
	size_t parent = (child - 1) / 2;
	//可能会持续上调
	//此处为小堆，若需要大堆，则只用调整if中的符号就行
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//更新关系
			child = parent;
			parent = (child - 1) / 2;
			//注意child=0时，parent=0,会陷入死循环。
			//无论用不用size_t，parent始终不会小于0
			//-1/2==0
		}
		//还应该考虑中间就停止的情况
		else
		{
			break;
		}
	}
}


//插入新数据后，要保持大根堆、小根堆的性质
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//空间不够，先扩容
	if (php->capacity == php->size)
	{
		size_t newCapacity = php->capacity * 2 + 1;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed.\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	//堆中插入数据——向上调整算法
	//第一步：先把新数据放在物理结构（顺序表/数组）的尾部
	php->a[php->size] = x;
	++php->size;
	//第二步：向上调整
	AdjustUp(php->a, php->size - 1);
}
void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; i++)
	{
		printf("%d ",php->a[i]);
	}
	printf("\n");
}

void AdjustDown(HPDataType* a,size_t size,size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		//第一步：选出左右孩子中较小的一个
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		//如果孩子小于父亲则交换，并继续往下调整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//删除堆顶数据（小堆-删除堆顶最小数据/大堆-删除堆顶的最大数据）
//要保持小堆/大堆的性质
//若直接前移剩余数据，则有问题：①破坏结构②时间复杂度为O（N）,不方便
//更优秀的方案：第一个数据先和最后一个数据进行对调->不必抹掉数据，直接size--即可->向下调整
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//第一步：根与最后一个数据进行交换
	Swap(&php->a[0], &php->a[php->size-1]);
	//第二步：删除数据
	--php->size;
	//第三步：向下调整
	//时间复杂度：O(logN)
	AdjustDown(php->a,php->size,0);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

main.c

#include"Heap.h"

void TestHeap()
{
	HP hp;
	HeapInit(&hp);
	HeapPush(&hp, 1);
	HeapPush(&hp, 5);
	HeapPush(&hp, 0);
	HeapPush(&hp, 8);
	HeapPush(&hp, 3);
	HeapPush(&hp, 9);
	HeapPrint(&hp);
	HeapPop(&hp);
	HeapPrint(&hp);
	HeapDesTroy(&hp);
}

//堆排序的步骤比较简单，即：
//将数组中的无序元素全部放到一个新建的堆中，再依次pop出，即得有序的元素列
//堆排序——升序
void HeapSort(HPDataType* a, int size)
{
	//第一步：建立一个堆（小堆）
	HP hp;
	HeapInit(&hp);
	//第二步：将数组中的无序数据都放到堆中
	//第三步：由于小堆可以依次弹出从小到大的数据，故依次放入数组即可
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);
	}
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDesTroy(&hp);
}

int main()
{
	TestHeap();
	HPDataType a[] = { 4,2,7,8,5,1,0,6 };
	HeapSort(a, sizeof(a) / sizeof(HPDataType));
	for (size_t i = 0; i <= 7; i++)
		printf("%d ", a[i]);
	return 0;
}