【数据结构】-向上调整算法和向下调整算法

【数据结构】-向上调整算法和向下调整算法

作者:小树苗渴望变成参天大树
作者宣言:认真写好每一篇博客
作者gitee:gitee

在这里插入图片描述

如 果 你 喜 欢 作 者 的 文 章 ,就 给 作 者 点 点 关 注 吧!

  • 前言
  • 一、堆的概念及结构
  • 二、堆的创建(以大根堆为例)
  • 三、堆的插入
  • 四、堆的删除
  • 五、堆顶的元素
  • 六、判断堆是否为空
  • 七、堆里有多少元素
  • 八、代码测试

前言

今天我们来堆,堆是建立再有二叉树基础的前提下去学习的,采用的是二叉树的顺序存储方式,所以结构类似于满二叉树,会介绍堆的概念,以及模拟一个堆出来,本篇知识量有一点大,希望读者可以耐心的阅读下去,并且真正学会堆


一、堆的概念及结构

如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺存储方式存储在一个一维数组中,并满足: <= 且 <= ( >= 且 >= ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:
1.堆中某个节点的值总是不大于或不小于其父节点的值;
2.堆总是一棵完全二叉树。
3.堆顶一定是整个堆中最大或者最小的数据

我们只需要看堆的性质即可
我们来看一下两种类型的堆

在这里插入图片描述

看到现在我们要掌握什么是堆,什么是大根堆,什么是小根堆,以及怎么通过堆写成数组的形式,怎么通过数组来写成堆的形式

注意:堆里面的元素如果都相等的话,即可以看成大根堆,也可以看成小根堆

二、堆的创建(以大根堆为例)

我们刚才说过对于堆我们采取数组的方式来存储,还要满足可以往堆里面插入和删除数据时必须还得是堆的情况,我们采取顺序表的创建方式来创建堆

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//定义一个数组
	int size;//数组里面的有效数据个数
	int capacity;//此时数组容量大小
}Heap;

初始化和顺序表初始化一样:

void HPInit(Heap* php)
{
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (php->a == NULL)
	{
		perror("malloc:");
		return;
	}
	php->size = 0;
	php->capacity = 4;
}

我们重点来介绍堆的插入和删除

三、堆的插入

我们插入数组的树必须保证原数组依然是堆,这就很有难度,我们先来看图讲解:

在这里插入图片描述

我们采取的是向上调整算法,肯定是先插入左孩子,再插入右孩子,所以插入的是右孩子不必考虑左孩子的值是否比父亲大等情况,我们只需要把插入的孩子和父亲比较就好了,当parent<0就结束,没有交换的时候表示已经是堆了,因为你再插入的之前他就是一个堆了

我们来看向上调整算法代码:

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)//传入的数组和插入的孩子再数组的下标
{
	assert(a);
	int parent = (child - 1) / 2;//找到父亲结点对应的下标
	while (child > 0)
	{
		if (a[parent] < a[child])//以大根堆为例,小根堆换一下符号即可
		{
			Swap(&a[parent], &a[child]);//交换
			child = parent;
			parent = (child - 1) / 2;//迭代
		}
		else
		{
			break;
		}
	}
}

因为都是一步步的向上进行调整,所有就叫向上调整算法

我们看堆的插入:

void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * 2 * php->capacity);
		if (tmp == NULL)
		{
			perror("realloc:");
			return;
		}
		else
		{
			php->a = tmp;
			php->capacity *= 2;
		}
	}
	php->a[php->size++] = x;//先插入,再把数组弄成堆的形式
	AdjustUp(php->a, php->size - 1);//向上调整算法
}

四、堆的删除

我们来想一下,堆的删除,应该还是删除那一个数据,是堆头还是堆尾,我们可以来想想,如果删除堆尾,有什么意义,即不一定是最大的数据,也不是最小的数据,没有什么意义,所以我们选择删除堆头的数据,那我们怎么去删除呢

有的人会想,再顺序表的时候,我们进行头删的时候,把前面的数据直接往前面挪一位,所以我们再堆的时候可不可以也这样搞,我们来画图看看:

在这里插入图片描述

我们发现采取挪数据的方式并不可取,父亲与孩子的关系全部乱了,那我们应该怎么去解决删数据的问题呢??

我们想到一种方法,因为插入数据是在尾部插入,插入之前是堆,不影响,那我们再删除的时候再从尾部删除不就可以了,但是我要删除的数据是堆顶的数据啊,怎么删除尾部的呢,我们可以交换一下,那交换了这个堆可能就不是堆了,但是堆里面的结点的那个对应关系是不是没有破坏,我们重新调整就好了
来看图:

在这里插入图片描述

我们看到我们采取的向下天正算法,把交换好的数据重新调整成堆,我们来直观的看一下向下调整算法的代码

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;//假设左孩子大
		while (child<n)
		{
			if (child + 1 < n && a[child] < a[child + 1])
			{
				child += 1;
			}
			if (a[parent] < a[child])
			{
				Swap(&a[parent], &a[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
}

不会的可以走读一下代码看看是怎么实现的
我们来看一下删除的完整代码:

void HeapPop(Heap* php)
{
	assert(php);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);//因为都是从堆顶调整,所以parent传的就是0
}

注意:向上调整算法和向下调整算法都有一个前提条件,被调整的那个结点,左右子树都必须是堆

对于堆的两款大骨头我们几乎啃完了,接下来大部分都是顺序表玩生下来的操作了

五、堆顶的元素

HPDataType* HeapTop(Heap* php)
{
	assert(php);
	return php->a[0];
}

六、判断堆是否为空

bool HeapEmtpy(Heap* php)
{
	assert(php);
	return php->size == 0;
}

七、堆里有多少元素

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

八、代码测试

int main()
{
	Heap php;
	HPInit(&php);
	HeapPush(&php,1);
	HeapPush(&php, 2);
	HeapPush(&php, 34);
	HeapPush(&php, 4);
	HeapPush(&php, 23);
	HeapPush(&php, 16);
	HeapPush(&php, 7);
	while (!HeapEmtpy(&php))
	{
		printf("%d ", HeapTop(&php));
		HeapPop(&php);
	}
}

在这里插入图片描述

我们看到我们手动模拟出来一个堆了,相信大家学到这里对堆有了不一样的理解

完整代码:

#include"Heap.h"
void HPInit(Heap* php)
{
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (php->a == NULL)
	{
		perror("malloc:");
		return;
	}
	php->size = 0;
	php->capacity = 4;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * 2 * php->capacity);
		if (tmp == NULL)
		{
			perror("realloc:");
			return;
		}
		else
		{
			php->a = tmp;
			php->capacity *= 2;
		}
	}
	php->a[php->size++] = x;
	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] < a[child + 1])
			{
				child += 1;
			}
			if (a[parent] < a[child])
			{
				Swap(&a[parent], &a[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
}
void HeapPop(Heap* php)
{
	assert(php);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}
HPDataType* HeapTop(Heap* php)
{
	assert(php);
	return php->a[0];
}
bool HeapEmtpy(Heap* php)
{
	assert(php);
	return php->size == 0;
}
int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;
void HPInit(Heap* php);
void HeapPush(Heap* php, HPDataType x);
void HeapPop(Heap* php);
HPDataType* HeapTop(Heap* php);
bool HeapEmtpy(Heap* php);
int HeapSize(Heap* php);
                       

点击阅读全文

上一篇 2023年 5月 26日 am10:23
下一篇 2023年 5月 26日 am10:24