【数据结构】堆（Heep）

啥也不会干的小码

已于 2024-07-19 21:31:37 修改

阅读量1.4k

点赞数 15

分类专栏： #c语言进阶(数据结构) 文章标签：数据结构 c语言

于 2024-05-17 00:58:36 首次发布

本文链接：https://blog.csdn.net/SWsunlight/article/details/138977378

版权

#c语言进阶(数据结构) 专栏收录该内容

13 篇文章

订阅专栏

✨✨✨专栏：数据结构

🧑‍🎓个人主页：SWsunlight

一、堆：

定义：

堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组对象。

性质：

1、总是一颗完全二叉树；

2、堆的某个节点的值总是大于等于或者小于等于其父亲节点；

大、小根堆：

要求的就是父子关系

大根堆：任何一个父亲结点>=孩子结点

孩子与自己爹谁大谁当爹

小根堆：所有的父亲结点<=孩子结点（倒反天罡）

孩子与自己爹谁小谁当爹

注意： 不一定是升序；因为只是要求的兄弟节点没有进行大小比较，那么兄弟的孩子可以比兄弟小，但可以比你大

特点：

》》根结点是最小（小堆）或者最大值（大堆）（可以用来找极值和排序，效率高）

二、实现堆（完全二叉树）：

前言：

需要实现的操作：

堆的定义
堆的初始化
堆的销毁
判空
数据交换
大、小堆向上调整
堆的插入
大堆插入
小堆插入
大、小堆向下调整
删除堆顶元素
大堆删除
小堆删除
查看堆顶数据
数据个数

因为大小堆有些实现函数是一样的，所以我将接口进行了细分；虽然大小堆插入和删除不同，但就是只是因为向上和向下调整的差别，所以我将上下调整和插入删除分别分装成2个接口，然后将2个接口放到一个专门的函数去调用各自需要的接口完成插入和删除

1、堆的定义：

a是指向数据域的指针（数组），size计数，capacity空间容量；创建方式：和顺序表一样

2、堆的初始化：

写了很多次了的问题：根据结构体成员进行一一初始化即可

3、销毁：

4、判空：

看数据个数，若是个数为0，返回true

5、交换数组中2个数据：

在下面的接口实现中，都要用到数组内数组的交换，因为你要满足堆的性质，根据需求保证父子关系

6、堆的插入：

先判断是否要扩容，然后就是在数组里放数据，插入要根据你的需求来：比如大堆的话，要保证孩子节点比它的父亲节点小，因为它的父亲比它父亲的父亲也要小，所以孩子节点要和它的祖先比较大小。才能完成一次插入，这里的插入并不完整

7、大、小堆向上调整:

将数据插到了堆的末尾，因为是根据下标顺序插的，可是我们要满足父子关系（堆的性质），那么必须要让插入的数据和自己的祖先都进行比较。以小堆堆为例：当该结点若是比自己的祖先都要大就不动它，若是它比自己的祖先小，就要和祖先换个位置“倒反天罡”

看图：一个参数接收数组，一个接收下标；为啥不接收结构体指针，因为我可将这个接口单独拿来进行堆排序；注意判断条件，我们要child>0,不要用parent>=0作为结束条件，因为child=0的时候，parent = -1/2 根据c中整数除法，最后的到结果就是parent = 0;有错误性

用到了公式

大堆的向上：同理的就是将数据比较变成小于变成了大于

8、堆的删除：

有点特殊，一般我们会想到将其根节点覆盖掉，就如下：我们发现了，结点关系全乱了，我的兄弟变成了我的爹，就是我拿你当兄弟，你想当我的义父

为了保证堆的性质不变，将最后一个结点和头互换，删除最后一个节点

9、大、小堆向下调整：

继续删除的操作，将堆顶根据需求进行下调。以小堆为例子：让左孩子和右兄弟进行比较，然后再和父亲比较，谁小谁当爹，直到满足堆的性质

当到最后一层时，有可能没有兄弟，所以一定要控制兄弟

用假设法，小的就是左孩子，然后就是右孩子的下标要控制在最后一个下标，parent是父亲结点

大堆类似，就是向下调要改个符号：父亲和2个孩子最大的孩子进行比较，若是比它大。就交换

提示：我们发现了不断删除操作，对于大堆堆顶：可以依次为最大次大 …… 最小的数

小堆堆顶：依次为最小，次小……最大的数

10、数据个数和取堆顶数据：

看一下

三、代码实现：

Heap.h头文件：

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

typedef int HpDataType;
//数组
typedef struct Heap {
	//数据
	HpDataType* a;
	int size;
	int capacity;
}Hp;

//交换数据
void Swp(HpDataType* p1, HpDataType* p2);

//初始化：
void HpInit(Hp* phead);

//销毁：
void HpDestroy(Hp* phead);

//判空：
bool HpEmpty(Hp* phead);

//大堆：向上调整
void AdjustUpBig(HpDataType* a,int child);
//大堆:向下调整:n表示的是数据个数，parent表示根节点（老祖宗）
void AdjustDownBig(HpDataType* a, int n,int parent);
//大堆：插入数据
void HpPushBig(Hp* phead, HpDataType x);
//大堆：删出数据
void HpPopBig(Hp* phead);


//小堆：向上调整,数组，孩子
void AdjustUpSmall(HpDataType* a, int child);
//小堆：向下调整，数组，孩子
void AdjustDownSmall(HpDataType* a, int n, int parent);
//小堆：插入数据
void HpPushSmall(Hp* phead, HpDataType x);
//小堆：删出数据
void HpPopSmall(Hp* phead);


//插入数据
void HpPush(Hp* phead,HpDataType x);
//删除数据：
void HpPop(Hp* phead);
//取数据：
HpDataType Hptop(Hp* phead);
//数据个数：
int Size(Hp* phead);

Heap.c源文件：

//初始化：
void HpInit(Hp* phead)
{
	//断言：判空！
	assert(phead);
	phead->a = NULL;
	phead->size = phead->capacity = 0;
}

//销毁：
void HpDestroy(Hp* phead)
{
	assert(phead);
	free(phead->a);
	phead->a = NULL;
	phead->size = phead->capacity=0;
}

//判空：
bool HpEmpty(Hp* phead)
{
	assert(phead);
	//数据个数为0，返回true（真）
	return phead->size == 0;
}
//大堆：向上调整,child 接受孩子
void AdjustUpBig(HpDataType* a, int child)
{
	assert(a);
	int  parent = (child - 1) / 2;
	//循环的进行从3个方面考虑：
	// 1、初始条件
	// 2、中间过程
	// 3、结束条件
	//循环有2种写法：
	while (child>0&&a[child]>a[parent])
	{		
		//互换；
		Swp(&a[child],&a[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}
	//while (child > 0)
	//{
	//	if (a[child] > a[parent])
	//	{
	//		//互换；
	//		Swp(&a[child],&a[parent]);
	//		child = parent;
	//		parent = (child - 1) / 2;
	//	}
	//	else
	//	{
	//		break;
	//	}
	//}
}
//大堆:向下调整
void AdjustDownBig(HpDataType* a, int n, int parent)
{
	assert(a);
	//用到假设法：我们要保证我的父亲节点比最大的儿子节点大或者相等；假设左孩子大
	int child = 2 * parent + 1;
	while (child < n)
	{//判断一下,完全二叉树，有可能会有有孩子不存在的情况
		if (a[child] < a[child + 1] && child + 1 < n)
		{
			//??孩子大
			child = child + 1;
		}
		if (a[child] > a[parent])
		{
			Swp(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
		
	}

}

//小堆：向上调整
void AdjustUpSmall(HpDataType* a, int child)
{
	assert(a);
	int  parent = (child - 1) / 2;
	//循环的进行从3个方面考虑：
	// 1、初始条件
	// 2、中间过程
	// 3、结束条件
	//循环有2种写法：
	while (child > 0 && a[child] < a[parent])
	{
		//互换；
		Swp(&a[child], &a[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}

}
//小堆：向下调整   n表示数据个数  parent父亲结点，开始时是0（堆顶）
void AdjustDownSmall(HpDataType* a, int n, int parent)
{
	assert(a);
	//用到假设法：我们要保证我的父亲节点比最小的儿子节点小或者相等；假设左孩子小
	int child = 2 * parent + 1;
	while (child < n)
	{//判断一下,完全二叉树，有可能会有有孩子不存在的情况
		if (a[child] > a[child + 1] && child + 1 < n)
		{
			//??孩子小
			child = child + 1;
		}
		//父亲比孩子大，进行交换
		if (a[child] < a[parent])
		{
			Swp(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}

	}
}

//插入数据
void HpPush(Hp* phead, HpDataType x)
{
	assert(phead);
	//先扩容：
	//若是没有则先给定义一个:没有则申请4个空间
	int newcapacity = (phead->capacity == 0 ? 4 : 2 * (phead->capacity));
	//查看空间够不够：当空间大小与有效数据个数相同时。说明空间不够
	if (phead->capacity == phead->size)
	{
		//要先申请空间：申请的内存为 容量*空间大小 
		HpDataType* pa = (HpDataType*)realloc(phead->a, newcapacity * sizeof(HpDataType));
		//判断申请是否成功：
		if (pa == NULL)
		{
			perror("realloc");
			return;
		}
		//成功了：
		//将空间给arr
		phead->a = pa;
		//将改好的空间容量赋值给capacity；
		phead->capacity = newcapacity;
	}
	//开始插入数据
	phead->a[phead->size++] = x;

}

//取数据：
HpDataType Hptop(Hp* phead)
{
	assert(phead);
	assert(phead->size > 0);
	
	return phead->a[0];
}
//数据个数：
int Size(Hp* phead)
{
	assert(phead);
	return phead->size;
}


//删除栈顶元素，先将栈顶元素和最后一个叶子节点交换
void HpPop(Hp* phead)
{
	assert(phead);
	assert(phead->size > 0);
	//叶子节点和老祖宗换一下，当所有人的祖宗
	Swp(&phead->a[0],&phead->a[phead->size-1]);
	phead->size--;
}

//交换数据
void Swp(HpDataType* p1, HpDataType* p2)
{
	assert(p1 && p2);
	HpDataType tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}

//大堆：插入数据
void HpPushBig(Hp* phead, HpDataType x)
{
	HpPush(phead, x);
	//向上进行调整:将最大的放到栈顶(传下标)
	AdjustUpBig(phead->a, phead->size - 1);

}
//大堆：删出数据
void HpPopBig(Hp* phead)
{
	HpPop(phead);
	//向下调整 然后进行交换，必须一直保持堆顶元素为最大；
	AdjustDownBig(phead->a, phead->size, 0);
}

//小堆：插入数据
void HpPushSmall(Hp* phead, HpDataType x)
{
	HpPush(phead, x);
	AdjustUpSmall(phead->a, phead->size - 1);
}
//小堆：删出数据
void HpPopSmall(Hp* phead)
{
	HpPop(phead);
	AdjustDownSmall(phead->a, phead -> size, 0);
}

test.c源文件：

#define _CRT_SECURE_NO_WARNINGS 3
#include"Heap.h"
//大堆：
void Test0()
{
	int arr[9] = { 1,12,4,5,7,8,9,10 };
	Hp pts;
	//初始化：
	HpInit(&pts);
	//Push
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		HpPushBig(&pts, arr[i]);
	}
	while (!HpEmpty(&pts))
	{
		//先取数据，在删除！！
		printf("%d ", Hptop(&pts));
		HpPopBig(&pts);
		
	}
	//销毁：
	HpDestroy(&pts);
}
//小堆：
void Test1()
{
	int arr[9] = { 1,12,4,5,7,8,9,10 };
	Hp pts;
	//初始化：
	HpInit(&pts);
	//Push
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		HpPushSmall(&pts, arr[i]);
	}
	while (!HpEmpty(&pts))
	{
		//先取数据，在删除！！
		printf("%d ", Hptop(&pts));
		HpPopSmall(&pts);
	}
	
	//销毁：
	HpDestroy(&pts);
}
//


int main()
{
	int arr[] = { 1,12,4,5,7,8,9,10 };
	int n = sizeof(arr) / sizeof(arr[0]);
	
	Test0();
	putchar('\n');
	Test1();
	return 0;
}

完结撒花