堆（heap）的概念及其实现

咬咬

发布于 2024-06-12 14:08:46

760

发布于 2024-06-12 14:08:46

文章被收录于专栏：学习笔记学习笔记

前言：

在学习完树后，我进入到堆的学习，总的来说堆就是一种特殊的树，以下是我对堆的一些总结和归纳：

概念:

堆：一种有特殊用途的数据结构--用来在一组变化频繁（增删查改频率高）的数据中查找最值

堆的物理层面：表现为一组连续的数组区间

堆的逻辑层面：一颗满完全二叉树

小堆和大堆：满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆；反之，则是小堆，或者小根堆，或者最小堆。当一个堆为大堆时，它的每一棵子树都是大堆

小堆要求：任意一个父亲<=孩子
大堆要求：任意一个父亲>=孩子
强调：没有中堆这个概念

堆的实现：

头文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int HPDateType;
typedef struct Heap
{
	HPDateType* a;
	int size;
	int capacity;
}Heap;
// 堆的构建
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestroy(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDateType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDateType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

初始化：

void HeapInit(Heap* hp)
{
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

销毁：

void HeapDestroy(Heap* hp)
{
	free(hp->a);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

堆的插入：

1.先判断空间是否充足，空间不够则需要扩容

2.将数据插入到最后一个位置

3.向上调整（重点）

向上调整思路图：

代码实现：

void Swap(HPDateType* x1, HPDateType* x2)
{
	HPDateType tmp = 0;
	tmp = *x1;
	*x1 = *x2;
	*x2 = tmp;
}
void AdjustUp(HPDateType* a,int child)
{
	int preant = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[preant])
		{
			Swap(&a[child], &a[preant]);
			child = preant;
			preant = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* hp, HPDateType x)
{
	assert(hp);
	if (hp->capacity == hp->size)//扩容
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDateType* tmp = (HPDateType*)realloc(hp->a, sizeof(HPDateType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	AdjustUp(hp->a, hp->size);//向上调整//小堆
	hp->size++;
}

现在可以在test.c中测试一下：

完美实现!

堆的删除：

在堆的删除中不是像以前一样删除最后一个元素，我们一般规定在堆的删除中是删除根节点，

所以堆的删除基本思路就是：

1.将根节点和最后一个元素交换

2.size--删除最后一个元素，也就是删除了之前的根节点

3.从根节点开始向下调整

向下调整基本思路：

代码实现：

void AdjustDown(HPDateType* a, size_t size, int n)//向下调整,n为父亲的下标
{
	int preant = n;
	int child = preant * 2 + 1;//先默认左孩子小于右孩子
	while (child<size)
	{
		if (a[child + 1] < a[child]&&child+1<size)//若右孩子小于左孩子，调整child
		{
			child++;
		}
		if (a[child] < a[preant])
		{
			Swap(&a[child], &a[preant]);
			preant = child;
			child = preant * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(Heap* hp)
{
	assert(hp);
	Swap(&hp->a[0], &hp->a[hp->size-1]);//将根和最后一个元素交换
	hp->size--;//删除最后一个元素，也就是之前的根
	AdjustDown(hp->a,hp->size,0);//向下调整，小堆
}

放入test.c中测试一下：

完美实现！

返回堆顶元素：

HPDateType HeapTop(Heap* hp)
{
	return hp->a[0];
}

返回堆内元素个数：

int HeapSize(Heap* hp)
{
	return hp->size;
}

判空:

int HeapEmpty(Heap* hp)
{
	return hp->size == 0;
}

最后一起放入test.c中检查一哈：

完美实现！

那么堆的实现就告一段落了，快自己打开编译器实践一下把。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-12，如有侵权请联系 cloudcommunity@tencent.com 删除

heap

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度