【初阶数据结构】——堆的引入

目录

前言

一、二叉树的顺序结构及实现 

1.1二叉树的顺序结构

1.2堆的结构

二、堆的实现

2.1堆向上调整算法（堆的插入）

2.2堆向下调整算法（堆的删除）

2.3建堆的时间复杂度

2.4堆的创建

2.5堆的初始化和空间的销毁

2.6堆的插入

向上调整函数

交换函数

2.7堆的删除

向下调整函数

2.8堆的打印、取值、判空

三、完整代码

前言

上篇文章简单介绍树，讲解了最基本的二叉树，以及二叉树使用数组存储的顺序结构和使用链表存储的链式结构两种存储方式，今天就引入堆来实现二叉树。

一、二叉树的顺序结构及实现 

1.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而满二叉树和完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

1.2堆的结构

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

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值。

大堆：任何父亲大于等于孩子

小堆：任何父亲小于等于孩子
堆总是一棵完全二叉树。

二、堆的实现

2.1堆向上调整算法（堆的插入）

我们直到在数组中插入数据是在末尾插入，那么用堆来表示就是在有效数据下面做孩子或者父亲，依次插入数据和上面的父亲结点作比较，如果父亲大了就将父亲和孩子互换，一直换到度也就是第一个结点就形成小堆，反之则形成大堆。 

2.2堆向下调整算法（堆的删除）

我么以上面建的小堆为例如果我们删除第一个元素，按照惯例将后面的元素前移，就会形成新的堆但是新的堆不一定是我们的大堆或者小堆上面的情况纯属巧合，通过观察我们可以发现去掉第一个元素形成的左右子树依然是小堆，我们不妨将第一个元素和最后一个元素互换位置，这样最小的元素就在最后，指针前移就可以做到删除，然后第一个位置的两个子树都是小堆再从两个小堆的堆顶选出最小的交换，重复操作又可以是一个小堆了。

2.3建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)： 

2.4堆的创建

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

还是使用动态开辟空间，来实现；

2.5堆的初始化和空间的销毁

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

和顺序表一样，将指针置空和将容量，size置零 。

//销毁空间
void HPDes(HP* php)
{
	assert(php);
	free(php->a);
	php->size = php->capacity = 0;
}

使用free库函数释放动态开辟的空间，最后将容量和size置零。

2.6堆的插入

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 failed");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	HPadjustUp(php->a, php->size-1);
}

和顺序表的形式差不多，进入函数判断空间是否足够，不够的话动态开辟新的空间，开辟不成功的话打印错误码并退出，成功的话插入有效数据，size++，然后使用向上调整函数调整成堆 。

向上调整函数

调整函数就是上面的堆的向上调整算法，运用父亲和孩子的下标关系调整。

void HPadjustUp(HPDatatype* a, int child)
{
	//找到父亲
	int parent = (child - 1) / 2;
	//根为0  当和根交换后child为0
	while (child > 0)
	{
		//当child小时和父亲交换 建成小堆
		//当child大时和父亲交换 建成大堆
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

交换函数

void swap(HPDatatype* x, HPDatatype* y)
{
	HPDatatype tmp = *x;
	*x = *y;
	*y = tmp;
}

取地址防止出函数创建的变量销毁，导致交换失败。

2.7堆的删除

void HPpop(HP* php)
{
	assert(php);
	assert(php->size);
	//先将头和尾交换  左右子树依然是完整的小/大堆，再从两个子堆中找出最大/小值；
	swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	HPadjustDown(php->a, php->size, 0);
}

 进入函数先判断，如果size为0是会造成越界，再将头和尾交换，size减减，最后使用堆的向下调整算法调整成小堆。

向下调整函数

void HPadjustDown(HPDatatype* a, int n, int parent)
{
	//假设左孩子最小
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			//假设失败 右孩子小
			++child;
		}
		else
		{
			if (a[child] < a[parent])
			{
				swap(&a[child], &a[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
 
		}
	}
}

在这个函数中我们使用了一个假设法我们也不知道子堆的堆顶那个数据最小，但是两者是连续的先假设一个然后进行判断 ；这里一定要注意child的取值范围（child

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

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

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

#define _CRT_SECURE_NO_WARNINGS 67
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDatatype;
typedef struct Heap
{
	HPDatatype* a;
	int size;
	int capacity;
}HP;
//初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
//销毁空间
void HPDes(HP* php)
{
	assert(php);
	free(php->a);
	php->size = php->capacity = 0;
}
void swap(HPDatatype* x, HPDatatype* y)
{
	HPDatatype tmp = *x;
	*x = *y;
	*y = tmp;
}
//
void HPadjustUp(HPDatatype* a, int child)
{
	//找到父亲
	int parent = (child - 1) / 2;
	//根为0  当和根交换后child为0
	while (child > 0)
	{
		//当child小时和父亲交换 建成小堆
		//当child大时和父亲交换 建成大堆
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
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 failed");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	HPadjustUp(php->a, php->size-1);
}
void HPPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
void HPadjustDown(HPDatatype* a, int n, int parent)
{
	//假设左孩子最小
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			//假设失败 右孩子小
			++child;
		}
		else
		{
			if (a[child] < a[parent])
			{
				swap(&a[child], &a[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
 
		}
	}
}
 
	
 
void HPpop(HP* php)
{
	assert(php);
	assert(php->size);
	//先将头和尾交换  左右子树依然是完整的小/大堆，再从两个子堆中找出最大/小值；
	swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	HPadjustDown(php->a, php->size, 0);
}
HPDatatype HPtop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
bool HPempty(HP* php)
{
	assert(php);
	
	return php->size == 0;
}
int main()
{
	HP hp;
	HPInit(&hp);
	int a[] = { 65,100,70,32,50,60 };
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}
	HPPrint(&hp);
	while (!HPempty(&hp))
	{
		printf("%d ", HPtop(&hp));
		HPpop(&hp);
	}
	HPDes(&hp);
	return 0;
}