【数据结构与算法】堆的讲解与实现超详细

CSCN新手听安

1630人浏览 · 2025-03-14 21:34:20

CSCN新手听安 · 2025-03-14 21:34:20 发布

堆的讲解与实现

小编个人主页详情<—请点击
小编个人gitee代码仓库<—请点击
数据结构与算法系列专栏<—请点击
倘若命中无此运，孤身亦可登昆仑，送给屏幕面前的读者朋友们和小编自己!

一、堆的概念讲解

如果有一个集合K={k₀,k₁,k₂,…………k_i-1,k_i-1}，将它的所有元素的值按照完全二叉树的存储形式存储到一个一维数组中：并且满足k_i>=k_i*2+1,k_i>=k_i*2+2(k_i<=k_i*2+1,k_i<=k_i*2+2)，那么我们称这个数组为大堆（小堆），将根节点最大的堆称为最大堆或大根堆，将根节点最小的堆称为最小堆或小根堆

大堆的父节点的值总是大于等于子节点的值
小堆的父节点的值总是小于等于子节点的值
堆一定是完全二叉树

在这里插入图片描述

二、堆的多文件管理

为了便于对堆进行维护，这里我们采用多文件管理

Heap.h包括了头文件，堆的结构体的定义，函数声明
Heap.c包括了堆的函数功能的实现
Test.c包括了堆的函数接口测试的基本框架

下面是小编要实现的堆的函数接口总览，往下阅读，跟上小编的节奏，下面小编将进行细致的讲解

//堆的初始化
void HeapInit(HP* php);
//堆的销毁
void HeapDestory(HP* php);
//交换
void Swap(HPDataType* x, HPDataType* y);
//向上调整
void AdjustUp(HPDataType* a, int child);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//堆的删除
void HeapPop(HP* php);
//堆的判空
bool HeapEmpty(HP* php);
//堆的大小
int HeapSize(HP* php);
//获取堆顶元素
HPDataType HeapTop(HP* php);

三、堆的实现

注意事项

小编这里默认实现的堆是大堆
注意区分本文中的堆指的是数据结构的堆它是一种功能性的结构，区别于操作系统中虚拟进程地址空间
我们使用结构体在栈上创建一个堆变量，堆结构体变量中的指针a指向操作系统虚拟进程地址空间中的堆的一块空间
我们是堆栈上面这块空间上的堆的结构体中的成员变量进行操作，需要传这个堆的结构体的地址，必须保证这个地址不为空，所以我们在实现函数结构的时候一定要进行断言确保传入函数的结构体的地址不为空

3.1堆的结构定义

堆的实现底层是一个数组，那么从实用性来讲，可以动态增长的数组相比静态数组更为实用，那么我们这里使用动态数组
既然涉及到数组，那么就会有增容，那么也就会有了两个变量，即当前数组有效个数大小size，数组的最大容量capacity
多种变量，我们将其封装在结构体中，便于使用
这里将存储的元素类型使用typedef进行重命名，提高代码的可维护性
对结构体名称进行重命名，便于书写

typedef int HPDataType;
//默认构建大堆
typedef struct Heap
{
	HPDataType* a;
	int capacity;
	int size;
}HP;

3.2堆的初始化

断言确保传入函数的地址不为空
使用指针a指向由malloc在堆上开辟的空间，初始开辟4个大小为4个字节的空间，检查确保指针a指向的不为空
由于初始开辟的是4个大小为4个字节的空间，所以初始容量为4
初始并没有存放数据，所以有效数据个数为0

void HeapInit(HP* php)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (php->a == NULL)
	{
		perror("malloc error");
		return;
	}

	php->capacity = 4;
	php->size = 0;
}

3.3堆的销毁

断言确保传入函数的地址不为空
使用free释放使用malloc开辟的空间
释放后将a置为空，防止野指针和非法访问内存
由于堆中的数据进行释放置空，那么容量和大小都要置为0

void HeapDestory(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	
	php->capacity = 0;
	php->size = 0;
}

3.4交换

由于Swap交换要多次使用，这里我们将其封装成一个函数
定义一个中间变量tmp用于交换指针x和y指向的地址上的数据即可

void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

3.5向上调整算法

在进行向上调整时要确保在入数据之前，数组中存储的本身就为大堆或小堆，如果只有一个元素也可看做大堆或小堆，这里我们以大堆为例进行讲解
我们在一个大堆的尾进行插入一个10，将10与它的父节点比较，如果大于它的父节点，那么调换它和父节点的位置
调换完成之后，继续再与它当前父节点进行比较，如果不大于则退出循环，如果仍然大于它的父节点如下图情况10>9，那么继续调换位置，
向上调整的本质就是调换数据，根据你要调换成为堆的性质，例如本文的大堆，则让大的元素向上调整，小的元素向下调整，小堆相反
首先传入的是你要向上调整的孩子节点的下标，那么要进行调整，那么就要算出其父亲节点的下标，利用公式进行计算即可
对于循环条件，这里建议使用parent >= 0来进行判断，以上图为例，parent==0，进入循环，判断10和9调换位置，调换完位置之后，迭代，child = parent，孩子节点被赋值为了0，那么使用公式再进行计算父亲节点的位置即（0-1）/2这个结果是-0.5，在计算机中进行整数都是舍弃小数部分，所以这里的parent成为了0，即父亲节点和孩子节点都为0，此时又进入了循环，孩子节点和父亲节点相等，进入else退出循环，也可以退出循环，但是这里如果没有break，是不是就死循环了，这里是以非正常代码跑出无误结果，虽然结果无误，但是小编还是建议采用正确的判断条件，即child>0进行判断，同样的以上面的情况进行讲解，此时父亲和孩子节点都为0，那么使用child>0进行判断，就不会进入循环，直接结束了循环，也就不会导致可能发生死循环的情况
上面讲解完循环条件的判断，接下来进入循环，我们要调整的是大堆，大堆要求父亲节点大于孩子节点，那么当还是节点大于父亲节点的时候就置换位置，或则就是父亲节点大于孩子节点，退出循环即可
置换完后进行迭代，将父亲节点位置的下标赋值给孩子，在重新使用孩子节点新的下标去找它新的父亲节点继续进行判断迭代即可

void AdjustUp(HPDataType* a,int child)
{
	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
		parent = (child - 1) / 2;
	}
}

3.6堆的插入

断言确保传入函数的地址不为空
由于堆的底层是数组，那么涉及数据插入的时候都应该检查是否满了，如果满了使用realloc函数进行扩容即可，扩容完不要忘记将对应容量也扩大2倍
size是数组的有效元素的个数，数组下标是从0开始的，所以size位置是要最后一个元素的下一个位置，在这个位置直接进行插入下x即可
由于插入了一个数据，那么此时元素有效个数加一，即size加一
此时仅仅是还是向数组内的插入了一个位置，我们这里要实现的是大堆，插入的这个数还要进行调整到它应该的位置上，这里调用向上调整算法即可，注意一点，我们要调整的元素的下标是原来的未加一的size的位置，由于size已经加一了，所以传入size-1即为我们插入了的元素的下标位置

void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc error");
			return;
		}

		php->a = tmp;
		php->capacity *= 2;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

3.7向下调整算法

在进行向下调整时要确保在入数据之前，数组中存储的本身就为大堆或小堆，如果只有一个元素也可看做大堆或小堆，这里我们以大堆为例进行讲解
向下调整算法是当堆需要删除数据的时候需要用到，例如，如果你想要删除9，那么你直接将9给删除了，你不能确保余下的数据是否还能够保持原有堆的性质，有可能可以保持例如下图情况可以保持，但是如果小编将3换为8是不是就不能保持原有的大堆的性质了，所以这种删除不可行
那么如果我们将堆顶的元素和堆的最后一个元素置换位置，就不存在这种情况了，置换完后，将元素个数减一，由于堆顶数据的访问是使用size进行限制的，所以这里size减一后就相当于将9给删除了，访问不到了
那么堆顶的根节点的左右子树仍然可以保持大堆的性质不变，此时只需要将2向下调整即可
再调整过程中由于要保证大堆的性质不变，大堆的根节点是最大的，所以要找出左右子树的根节点7，3较大的作为根节点，即7，这里我们采用假设法进行寻找，假设7节点是大的，3节点是小的，进行判断是否真的大于，如果不大于，那么就将child加一即可即为右子树的根节点的下标，这里进行判断后显然不用进行置换，7就为左右子树根节点的较大值，这里有一个细节，如果不存在右子树，即child已经是数组最后一个元素了，不存在右子树，那么有可能出现越界的情况，那么此时进行要进行判断child+1<n进行限制
当我们找出左右子树的根节点的较大值后与树的根节点进行比较，如果根节点小于孩子节点，那么置换否则就退出
再继续向下迭代循环即可，这里的循环判断条件要限制为child<n，如果child一旦大于等于所访问到的数据并非堆的数据并且可能越界了，不符合我们的要求，所以要限制child<n

在这里插入图片描述

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;

	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}

		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

3.8堆的删除

断言确保传入函数的地址不为空
当堆中没有数据的时候我们无法进行删除，使用堆的判空函数断言一下确保堆中有数据
删除详解请见3.7向上调整算法，我们要将堆的根节点进行向下调整，根节点的数组下标为0，传入向下调整算法即可

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

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

	AdjustDown(php->a, php->size, 0);
}

3.9堆的判空

断言确保传入函数的地址不为空
如果size等于0那么就是没有数据，==返回结果为1，也就是判空函数判断为真
如果size不等于0那么就是有数据，==返回结果为0，也就是判空函数判断为假

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

3.10堆的数据个数

断言确保传入函数的地址不为空
这里直接返回堆的数据个数即可

int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

3.11获取堆顶元素

断言确保传入函数的地址不为空
当堆的数据为空的时候，我们无法再继续进行数据的读取了，所以这里需要调用判空函数进行断言，确保读取数据的时候堆不为空
堆的根节点的就为根结构体中的存储的指针指向的数组中的第一个元素，下标为0，这里使用0+[]访问下标为0的元素直接返回即可

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

四、所有函数接口的可行性测试

创建堆，调用初始化函数，调用插入函数依次插入1，16，14，2，3，删除三个数据，打印当前堆的根节点数据，最后销毁

void TestHeap()
{
	HP hp;
	HeapInit(&hp);

	HeapPush(&hp, 1);
	HeapPush(&hp, 16);
	HeapPush(&hp, 14);
	HeapPush(&hp, 2);
	HeapPush(&hp, 3);

	HeapPop(&hp);
	HeapPop(&hp);
	HeapPop(&hp);

	printf("%d\n", HeapTop(&hp));

	HeapDestory(&hp);
}

如图所示，结果无误，所有函数接口正确

五、堆实现的源代码

Heap.h

#pragma once

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

typedef int HPDataType;
//默认构建大堆
typedef struct Heap
{
	HPDataType* a;
	int capacity;
	int size;
}HP;

//堆的初始化
void HeapInit(HP* php);
//堆的销毁
void HeapDestory(HP* php);
//交换
void Swap(HPDataType* x, HPDataType* y);
//向上调整
void AdjustUp(HPDataType* a, int child);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//堆的删除
void HeapPop(HP* php);
//堆的判空
bool HeapEmpty(HP* php);
//堆的大小
int HeapSize(HP* php);
//获取堆顶元素
HPDataType HeapTop(HP* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS

#include "Heap.h"

void HeapInit(HP* php)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (php->a == NULL)
	{
		perror("malloc error");
		return;
	}

	php->capacity = 4;
	php->size = 0;
}

void HeapDestory(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	
	php->capacity = 0;
	php->size = 0;
}

void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

void AdjustUp(HPDataType* a,int child)
{
	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
		}
		else
		{
			break;
		}
		child = parent;
		parent = (child - 1) / 2;
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc error");
			return;
		}

		php->a = tmp;
		php->capacity *= 2;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;

	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}

		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

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

	AdjustDown(php->a, php->size, 0);
}

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

Test.c

#define _CRT_SECURE_NO_WARNINGS

#include "Heap.h"

void TestHeap()
{
	HP hp;
	HeapInit(&hp);

	HeapPush(&hp, 1);
	HeapPush(&hp, 16);
	HeapPush(&hp, 14);
	HeapPush(&hp, 2);
	HeapPush(&hp, 3);

	HeapPop(&hp);
	HeapPop(&hp);
	HeapPop(&hp);

	printf("%d\n", HeapTop(&hp));

	HeapDestory(&hp);
}

int main()
{
	TestHeap();

	return 0;
}