堆的实现（C语言版）

堆的概念上个文章已经有过介绍了，简单的说就是一个完全二叉树，接下来我们主要来实现它。

一.选择实现方法

关于堆的实现，我们可以通过数组实现，也可以通过链表实现，由于链表过于浪费空间，而且我们可以简单的通过数组实现，就没必要用链表来实现，数组实现大家可能会想到是静态的还是动态的，我建议大家直接进行动态数组实现，之前顺序表我们两种都实现过了，而堆可以说和顺序表的结构体大体一样，这里就直接上手动态了。

二.实现过程

第一步：建立结构体

这一步和顺序表一样，就直接写出代码了。

//堆即是完全二叉树
//完全二叉树结构体定义
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

第二步：实现初始化接口和销毁接口

简单内容，直接上代码

//堆初始化接口定义
void HeapInit(HP* php)
{
	php->a = NULL;
	php->capacity = php->size = 0;
}

//堆销毁接口定义
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

第三步：（难点来了）实现堆的插入

我们这里是动态数组，所以，插入首先要进行的是扩容检查与扩容操作，这个是简单的，如下：

//空间开辟
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)
	{
		exit(-1);
	}
	else
	{
		php->a = tmp;
		php->capacity = newcapacity;
	}
}

下面插入元素，由于是数组，我们先插入到数组的尾部，再进行调整，所以，这里插入直接插到尾部即可：

//插入
php->a[php->size] = x;
php->size++;

注意：数组下标与size的关系

插入完了，现在就要进行调整了，由于这是树，并且是完全二叉树，那么调整是不是只能用父与子来进行，肯定不能是堂兄弟调整，而父子有一个公式：

leftchild = parent*2+1;
childright = parent*2+2;

parent=(child-1)/2;//不管左右孩子

所以我们就可以用一个向上调整法来实现，注意：你必须明确你是在建立大堆还是小堆，因为这里非常容易出错

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
	//我们这里是实现小堆
	int parent = (child - 1) / 2;//由关系公式的
	//while (child>0)//终止条件
	while (parent >= 0)//两种写法
	{
		if (a[child] < a[parent])//由于建立小堆，孩子比父亲小，要交换位置
		{
			Swap(&a[child], &a[parent]);//交换位置函数
			child = parent;//原来的父亲位置是孩子现在位置，要再和上比较
			parent= (child - 1) / 2;//现在父亲位置
		}
		else
		{
			break;
		}
	}
}

总体看看：

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
	//我们这里是实现小堆
	int parent = (child - 1) / 2;//由关系公式的
	//while (child>0)//终止条件
	while (parent >= 0)//两种写法
	{
		if (a[child] < a[parent])//由于建立小堆，孩子比父亲小，要交换位置
		{
			Swap(&a[child], &a[parent]);//交换位置函数
			child = parent;//原来的父亲位置是孩子现在位置，要再和上比较
			parent= (child - 1) / 2;//现在父亲位置
		}
		else
		{
			break;
		}
	}
}
//堆插入接口定义
void HeapPush(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)
		{
			exit(-1);
		}
		else
		{
			php->a = tmp;
			php->capacity = newcapacity;
		}
	}
	//插入
	php->a[php->size] = x;
	php->size++;
	//调整
	//向上调整法
	int child = php->size - 1;
	AdjustUp(php->a, child);
}

第四步：实现堆的删除

注意我们这里的堆删除是指堆顶，并非数组最后一个元素

首先我们要先进行首尾元素交换

Swap(&php->a[0], &php->a[php->size - 1]);

接下来尾删?

php->size--;

接下来由于堆顶元素与其他元素可能不满足堆的要求，所以我们要进行向下调整

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(HPDataType* a, int size, int parent)
{
	//注意我们这里是小堆奥
	//我们父与子交换条件是：父亲大于儿子，儿子可能有两个，所以我们要找小的，不然还要调整
	int 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;
		}
	}
}

第五步：实现取堆顶的元素

简单，直接上代码

//取出树根位置的数据定义
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->a);
	return php->a[0];
}

第六步：实现判断是否为空和确定堆元素个数

//堆中数据个数定义
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

三.验证代码正确性

这个过程非常重要，本来应该是边实现边验证的，由于我这里要保证代码连贯性讲解，所以放一起来验证，但是希望大家还是边实现边验证的，不然，出现很多问题可能让你崩溃。

首先，我们来验证初始化，插入和销毁接口

void Print(HP* php, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
void test()
{
	HP s1;
	int a[] = {4,6,2,1,5,8,2,9};
	HeapInit(&s1);
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		HeapPush(&s1, a[i]);
	}
	Print(&s1, sizeof(a) / sizeof(int));
	HeapDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

结果为堆，如下：

下面我们来验证堆的删除和取堆顶元素接口

void test()
{
	HP s1;
	int a[] = {4,6,2,1,5,8,2,9};
	HeapInit(&s1);
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		HeapPush(&s1, a[i]);
	}
	int k = 6;
	while (k--)
	{
		printf("%d ", HeapTop(&s1));
		HeapPop(&s1);
	}
	HeapDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

结果：

最后，我们在验证下判空吧

void test()
{
	HP s1;
	int a[] = {4,6,2,1,5,8,2,9};
	HeapInit(&s1);
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		HeapPush(&s1, a[i]);
	}
	while (!HeapEmpty(&s1))
	{
		printf("%d ", HeapTop(&s1));
		HeapPop(&s1);
	}
	printf("\n");
	HeapDestroy(&s1);
}
int main()
{
	test();
	return 0;
}

结果：

对于其他的大家可以自行验证，这里就不进行其他验证了。

四.代码完全版

这是Heap.c文件

#include "Heap.h"
void Print(HP* php, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

//堆初始化接口定义
void HeapInit(HP* php)
{
	php->a = NULL;
	php->capacity = php->size = 0;
}
//堆销毁接口定义
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
	//我们这里是实现小堆
	int parent = (child - 1) / 2;//由关系公式的
	//while (child>0)//终止条件
	while (parent >= 0)//两种写法
	{
		if (a[child] < a[parent])//由于建立小堆，孩子比父亲小，要交换位置
		{
			Swap(&a[child], &a[parent]);//交换位置函数
			child = parent;//原来的父亲位置是孩子现在位置，要再和上比较
			parent= (child - 1) / 2;//现在父亲位置
		}
		else
		{
			break;
		}
	}
}
//堆插入接口定义
void HeapPush(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)
		{
			exit(-1);
		}
		else
		{
			php->a = tmp;
			php->capacity = newcapacity;
		}
	}
	//插入
	php->a[php->size] = x;
	php->size++;
	//调整
	//向上调整法
	int child = php->size - 1;
	AdjustUp(php->a, child);
}
void AdjustDown(HPDataType* a, int size, int parent)
{
	//注意我们这里是小堆奥
	//我们父与子交换条件是：父亲大于儿子，儿子可能有两个，所以我们要找小的，不然还要调整
	int 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;
		}
	}
}
// 规定删除堆顶（根节点）
void HeapPop(HP* php)
{
	assert(php);
	//首尾交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	//尾删
	php->size--;
	//向下调整法
	AdjustDown(php->a, php->size, 0);
}

//取出树根位置的数据定义
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->a);
	return php->a[0];
}
//堆中数据个数定义
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

Heap.h文件：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 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;
//堆初始化接口声明
void HeapInit(HP* php);
//堆销毁接口声明
void HeapDestroy(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);

最后，这里给大家提一个问题，如果我是实现大堆呢？基于上述代码，应该如何改动呢？

小编祝福大家：Merry Christmas,拜拜！