二叉树——堆（C语言实现）

有礼貌的灰绅士

发布于 2023-03-28 15:19:26

6160

发布于 2023-03-28 15:19:26

文章被收录于专栏：C++与Linux的学习之路

小堆

小堆的结构与初始化

小堆的结构是子节点不小于父节点，兄弟结点没有顺序，并且总是完全二叉树。逻辑结构是这样的：

物理储存我们用顺序表来储存：首先从结点的祖先10开始，放进顺序表中，然后是他的子节点15和20，再往下访问也是访问15和20的子节点，分别是30，20，25，90，按照这个规律放进顺序表中就可以了。

[10,15,20,30,20,25,90,40,30,70];

首先创建一个顺序表的结构体

typedef int SD;//方便以后更改数组的数据类型
typedef struct pile
{
	SD* a;//数组
	int size;//数组有效值的长度
	int capacity;//数组容量大小
}pile;

初始化

void initialize(pile* hp)//初始化
{
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

堆的销毁，空判定，打印

销毁

void HeapDestory(pile* hp)//销毁
{
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

判断是否为空 空返回0，非空返回非0.

int HeapEmpty(pile* hp)//判断空
{
	return hp->size;
}

打印这里只打印整理后的数组：

void Pintf(pile* hp)//打印
{
	assert(hp);
	int i = 0;
	for (i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
}

插入，删除

插入物理结构是在顺序表中末尾插入一个数据。比如说我们插入一个5.

但是如果插入之后就不是小堆的结构了，祖先不小于等于新增元素，所以我们需要将5向上调整。（红线是调整顺序）

调成之后是这样的：

void swap(SD* p1,SD* p2)//交换数据
{
	SD p = *p1;
	*p1 = *p2;
	*p2 = p;
}
void HeapPush(pile* hp, SD x)//插入
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		int sum = hp->capacity == 0 ? 4 : hp->capacity * 2;
		SD* p = (SD* )realloc(hp->a, sum * sizeof(SD));
		if (p == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = p;
		hp->capacity = sum;
	}
	hp->a[hp->size] = x;//插入数据
	hp->size++;//记录数组的有效长度
	int child = hp->size - 1;//新插入的元素,元素的下标
	int parent = (child - 1) / 2;//新插入的元素的父节点,父节点的下标
	while (child > 0)//孩子的下标如果等于0就说明到堆顶了
	{
		if (hp->a[child] < hp->a[parent])//如果孩子比父节点小就交换
		{
			swap(&(hp->a[child]), &(hp->a[parent]));//交换
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;//如果不成立就说明已经是小堆了
		}
	}
}

删除删除第一个元素。

因为要保持原来小堆的形态，所以要让10到删除的那个位置，20不行，然后是15补刀10的位置，以此类推。（向下调整算法）

最后变成了这样：

代码是这个操作我们需要将头和尾先交换一下，然后删除尾再向下调整。

void HeapPop(pile* hp)//删除
{
	assert(hp);
	assert(HeapEmpty(hp));//判断是否为空
	swap(&hp->a[hp->size - 1], &hp->a[0]);//交换首尾的位置
	hp->size-- ;//删掉末尾的数
	int parent = 0;//父结点下标
	int minchild = 2 * parent + 1;//表示最小的孩子，第一次先假设左孩子最小
	while (minchild < hp->size)//防止数组越界
	{
		if (minchild+1 < hp->size && hp->a[minchild + 1] < hp->a[minchild])//防止右孩子出界
		{
			minchild = minchild++;//如果右孩子比左孩子小就让右孩子等于最小
		}
		if (hp->a[minchild] < hp->a[parent])//判断是否需要向下调整
		{
			swap(&hp->a[minchild], &hp->a[parent]);
			parent = minchild;
			minchild = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

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

原始发表：2022-09-14，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树