数据结构——堆（存储完全二叉树）

目录

一、堆的概念

二、堆的一些性质

三、堆的结构定义

四、堆的初始化

五、堆打印

六、向上调整算法

七、堆的插入

八、向下调整算法

九、堆的删除

十、取堆顶元素

十一、求堆大小

十二、堆判空

十三、测试代码

一、堆的概念

堆是一种顺序存储完全二叉树的数据结构。

二、堆的一些性质

堆分为小堆和大堆：

小堆要求父亲结点数据小于孩子结点；

大堆要求父亲结点数据小于孩子结点。

如何根据孩子结点下标找到父亲结点？

parent = (child - 1) / 2

如何根据父亲结点下标找到孩子结点？

child = 2 * parent + 1 （左孩子）

三、堆的结构定义

堆的结构中包含数组、堆大小、堆容量

//堆的结构定义
typedef int HPDataType;

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

四、堆的初始化

将数组初始化为空，堆大小和容量都初始化为0

//堆的初始化
void HPInit(HP* php)
{
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

五、堆打印

打印数组

//堆打印
void HPPrint(HP* php)
{
    assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

六、向上调整算法

孩子结点与父亲结点比较，如果孩子结点小于父亲结点，就将孩子结点与父亲结点交换。

注意第二个循环条件：是 child > 0，为什么不是 parent >=0 呢？

因为parent最小是0，永远不会小于0。但是该代码也能跑，因为当parent为0时，重置下标时，child重置为0，而parent = (child - 1) / 2也重置为0，此时a[child] = a[parent]，因此循环结束。

//向上调整算法
void AdjustUp(HPDataType*a, int child)
{
	int parent = (child - 1) / 2;
	while (a[child] < a[parent] && child > 0)//孩子结点比父亲结点小
	{
		//交换父亲结点和孩子结点的数据
		HPDataType tmp = a[child];
		a[child] = a[parent];
		a[parent] = tmp;

		//父亲结点和孩子结点下标重置
		child = parent;
		parent = (child - 1) / 2;
	}
}

七、堆的插入

插入数据前先检查堆容量是否足够，容量不够则扩容，容量足够则将数据存入数组中，再用向上调整算法将新插入的数据进行调整。

//堆的插入
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//堆扩容
	if (php->size ==php->capacity )
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size++] = x;

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

八、向下调整算法

将父亲结点与孩子结点比较，如果父亲结点大于孩子结点，则交换

由于可能有两个孩子结点，先要确认右孩子是否存在，如果存在取较小的孩子结点与父亲结点交换

//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size)//存在右孩子
		{
			if (a[child + 1] < a[child])//右孩子比左孩子小，用右孩子顶替父亲结点位置
			{
				child = child + 1;
			}
		}
		if (a[child] < a[parent])
		{
			//交换父亲结点与孩子结点
			HPDataType tmp = a[child];
			a[child] = a[parent];
			a[parent] = tmp;
			//重置父亲结点和孩子结点
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

九、堆的删除

堆的删除是删除堆顶元素，因为删除堆尾元素是没有意义的。

删除堆顶即删除二叉树的根，删除后还要使之成为一个完全二叉树，所以需要用次小值去顶替堆顶的位置。

具体方法：

先将堆尾元素与堆顶元素交换位置，然后删除堆尾元素，再利用向下调整算法将堆顶位置元素向下调整到合适的位置。

//堆的删除
void HPPop(HP* php)
{
	assert(php);
	assert(php->size);//空堆不可删除
	
	//交换堆顶元素和堆底元素
	HPDataType tmp = php->a[0];
	php->a[0] = php->a[php->size - 1];
	php->a[php->size - 1] = tmp;

	//删除堆底元素
	php->size--;

	//向下调整算法
	AdjustDown(php->a, php->size, 0);
}

十、取堆顶元素

先判断堆是否为空，不空则返回堆顶元素

//取堆顶元素
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size);

	return php->a[0];
}

十一、求堆大小

返回size即可

//求堆大小
size_t HPSize(HP* php)
{
	assert(php);
	return php->size;
}

十二、堆判空

利用size判断堆是否为空

//判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

十三、测试代码

void test01()
{
    //创建堆
    HP hp;
    //初始化堆
    HPInit(&hp);
    //堆插入
    HPPush(&hp, 1);
    HPPush(&hp, 5);
    HPPush(&hp, 3);
    HPPush(&hp, 6);
    HPPush(&hp, 7);
    HPPush(&hp, 5);
    HPPush(&hp, 4);
    HPPush(&hp, 9);
    HPPush(&hp, 8);
    //堆打印
    HPPrint(&hp);
    //堆插入
    HPPush(&hp, 1);
    //堆打印
    HPPrint(&hp);
    //堆删除
    HPPop(&hp);
    //堆打印
    HPPrint(&hp);
    //取堆顶元素
    printf("%d\n", HPTop(&hp));
    //求堆大小
    printf("%zd\n", HPSize(&hp));
    //堆判空
    if (HPEmpty(&hp))
        printf("空\n");
    else
        printf("非空\n");
}

int main()
{
    test01();
    return 0;
}