数据结构第十一弹---堆

1、堆的概念及结构

堆就是以二叉树的顺序存储方式来存储元素，同时又要满足父亲结点存储数据都要大于等于儿子结点存储数据（也可以是父亲结点数据都要小于等于儿子结点数据）的一种数据结构。堆只有两种即大堆和小堆，大堆就是父亲结点数据大于等于儿子结点数据，小堆则反之。

2、堆的性质

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

3、堆的调整算法

3.1、向下调整算法

现在我们给出一个数组，逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

但是，使用向下调整算法需要满足一个前提：
?若想将其调整为小堆，那么根结点的左右子树必须都为小堆。
?若想将其调整为大堆，那么根结点的左右子树必须都为大堆。
?
?

向下调整算法的基本思想（小堆）：
?1.从根结点处开始，选出左右孩子中值较小的孩子。
?2.让小的孩子与其父亲进行比较。
?若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
?若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了。

代码实现

void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}
void AdjustDown(HPDataType* a, int size, int parent)
{
	//1.假设左孩子为小的数据
	int child = parent * 2 + 1;
	while (child < size)
	{
	//2.如果左孩子>右孩子 则将右孩子赋值
	//有可能只有左孩子 所以加条件
	//以下未有左右孩子且左孩子>右孩子情况，则将child++
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		//3.将孩子与父亲进行比较 如果孩子小则交换
		//然后将父亲和孩子移动到下一个位置
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

交换数值函数注意

使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆呢？
?答案很简单，我们只需要从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整即可。
?

向下调整算法的时间复杂度：

根据计算可知，向下调整算法的时间复杂度为O(N)。

3.2、向上调整算法

当我们在一个堆的末尾插入一个数据后，需要对堆进行调整，使其仍然是一个堆，这时需要用到堆的向上调整算法。

向上调整算法的基本思想（小堆）：
?1.将目标结点与其父结点比较。
?2.若目标结点的值比其父结点的值小，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是小堆了。

但是，使用向上调整算法需要满足一个前提：
?若想将其调整为小堆，那么原来的数据为小堆。
?若想将其调整为大堆，那么原来的数据为大堆。
?
?代码实现

void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}
void AdjustUp(HPDataType* p, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (p[parent] > p[child])
		{
			Swap(&p[parent], &p[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向上调整算法时间复杂度

因此向上调整算法的时间复杂度为O(N*logN)。

4、堆的实现

实现一个数据结构的第一步需要创建一个工程。(下图为vs 2022)

Heap.h（堆的类型定义、接口函数声明、引用的头文件）
Heap.c（堆接口函数的实现）
test.c （主函数、测试顺序表各个接口功能）

4.1、头文件包含和结构定义

以下是实现堆可能用到的头文件。

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

堆的结构定义

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//存放数据的动态数组
	int size;     //有效数据个数
	int capacity; //数组容量
}HP;

4.2、初始化

void HeapInit(HP* php)
{
	assert(php);//断言避免出现空指针
	php->a = NULL;
	php->capacity = php->size = 0;
}

4.3、销毁

void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);//释放动态数组
	php->size = php->capacity = 0;
}

4.4、插入数据

插入数据的同时需要保证插入之后的数据依然是堆，由于插入数据之前的所有数据是堆，可以使用向上调整数据进行调整。

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//1.检查容量
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	//2.插入数据
	php->a[php->size] = x;
	php->size++;

	//3.调整数据
	AdjustUp(php->a, php->size-1);
}

测试

4.5、删除数据 删除堆顶

删除堆顶元素，首先需要有数据，通过断言判断，有数据的情况下先将堆顶元素和数组尾的数据进行交换，然后将size–，因为除了堆顶元素不满足堆结构之外，其他都满足，所以使用向下调整数据算法。

void HeapPop(HP* php)
{
	assert(php);
	//有数据才删除
	assert(php->size > 0);
	//1.将首位数据交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	//2.删除尾数据
	php->size--;
	//3.向下调整
	AdjustDown(php->a, php->size, 0);
}

测试

4.6、获取堆顶元素

根据堆的定义可知，堆顶元素就是数组首元素，返回首元素即可。

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

测试

4.7、获取有效数据个数

根据堆的结构设计，size就是堆的有效数据个数，返回size即可。

size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

测试

4.8、判断是否为空

根据堆结构的设计，size代表堆的有效数据个数，size等于0则为空，不等于0则不为空。

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

5、代码汇总

5.1、Heap.h

#pragma once     //防止头文件重复包含
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//存放数据的数组
	int size;     //有效数据个数
	int capacity; //数组容量
}HP;

//初始化
void HeapInit(HP* php);
//销毁
void HeapDestory(HP* php);
//插入数据
void HeapPush(HP* php, HPDataType x);
//删除数据 删除堆顶数据
void HeapPop(HP* php);
//取堆顶元素
HPDataType HeapTop(HP* php);
//获取有效数据个数
size_t HeapSize(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//两个元素交换
void Swap(HPDataType* a, HPDataType* b);

//向上调整数据 小堆
void AdjustUp(HPDataType* p, int child);
//向下调整算法 小堆
void AdjustDown(HPDataType* a, int size, int parent);

5.2、Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
//初始化 小堆
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}
//销毁
void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->size = php->capacity = 0;
}
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}
log N
//向上调整数据 小堆
void AdjustUp(HPDataType* p, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (p[parent] > p[child])
		{
			Swap(&p[parent], &p[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


//插入数据
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//1.检查容量
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	//2.插入数据
	php->a[php->size] = x;
	php->size++;

	//3.调整数据
	AdjustUp(php->a, php->size-1);
}

//向下调整算法 小堆
void AdjustDown(HPDataType* a, int size, int parent)
{
	//1.假设左孩子为小的数据
	int child = parent * 2 + 1;
	while (child < size)
	{
	//2.如果左孩子>右孩子 则将右孩子赋值
	//有可能只有左孩子 所以加条件
	//以下未有左右孩子且左孩子>右孩子情况，则将child++
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		//3.将孩子与父亲进行比较 如果孩子小则交换
		//然后将父亲和孩子移动到下一个位置
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//删除数据 删除堆顶数据
void HeapPop(HP* php)
{
	assert(php);
	//有数据才删除
	assert(php->size > 0);
	//1.将首位数据交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	//2.删除尾数据
	php->size--;
	//3.向下调整
	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;
}

总结

本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！