【初阶数据结构】实现顺序结构二叉树-＞堆（附源码）

2024-11-03 09:25:45

文章目录

须知

???? 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

???? 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
???? 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对数据结构感兴趣的朋友，让我们一起进步！

⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性。

1.堆的概念与结构

如果有⼀个关键码的集合 K = { k 0 , k 1 , k 2 , ... ， k n −1 } ，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜： K i <= K 2∗ i +1 （ K i >= K 2∗ i +1 且 K i <= K 2∗ i +2 ），i = 0、 1 、 2... ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆

叫做最⼩堆或⼩根堆。

1.1 堆的性质

• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；

• 堆总是⼀棵完全⼆叉树。

1.1.1 ⼆叉树性质

• 对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从

0 开始编号，则对于序号为 i 的结点有：

1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点（通常称为父节点）

2. 若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦

3. 若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

2 堆的模拟实现

底层：使用数组，进行了特殊的处理成为堆。

下面将以建立小堆为示例：

heap.h头文件下的函数声明和其它头文件

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

//定义堆的结构---数组

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;//有效的数据个数
	int capacity;//空间大小
}HP;

void HPInit(HP* php);
void HPDestroy(HP* php);

void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);

HPDataType HPTop(HP* php);
// 判空
bool HPEmpty(HP* php);

测试文件：

#include"Heap.h"

void test01()
{
	HP hp;
	HPInit(&hp);
	
	int arr[] = { 17,20,10,13,19,15 };
	for (int i = 0; i < 6; i++)
	{
		HPPush(&hp, arr[i]);
	}

	//HPPop(&hp);

	while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}


	HPDestroy(&hp);
}

int main()
{
	test01();
	return 0;
}

heap.c函数的实现方法（重点）

2.1 堆的初始化和销毁

void HPInit(HP* php)//初始化
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

void HPDestroy(HP* php)//销毁
{
	assert(php);
	if (php->arr)
		free(php->arr);

	php->arr = NULL;
	php->size = php->capacity = 0;
}

2.2 入堆操作

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//判断空间是否足够
	if (php->size == php->capacity)
	{
		//扩容
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	php->arr[php->size] = x;
	
	AdjustUp(php->arr, php->size);

	++php->size;
}

2.2.1 向上调整算法

入堆之后，可能现在堆的数据不符合小堆或大堆的特性，需要从新调整堆的结构。

因此向上调整算法产生。

将新数据插⼊到数组的尾上，再进⾏向上调整算法，直到满⾜堆。

向上调整算法

• 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后

• 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可

步骤（如下图）

代码如下:

void AdjustUp(HPDataType* arr,int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}	
}

2.3 堆的判空

// 判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

2.4 出堆

将堆顶与最后一个数据交换，交换完成有效数据个数-1，在进行向下调整算法，因为可能删除后的数据结构不符合堆的特性。

出堆（删除数据）：只能删除堆顶数据。

void HPPop(HP* php)
{
	assert(php && php->size);

	//arr[0]  arr[size-1]
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	--php->size;
	AdjustDown(php->arr, 0, php->size);
}

2.4.1 向下调整算法

void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	//while (parent < n)
	while (child < n)
	{
		//找左右孩子中找最小的
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.5 取堆顶数据

HPDataType HPTop(HP* php)
{
	assert(php && php->size);
	return php->arr[0];
}

2.6 获取堆有效数据个数

//获取堆中有效数据个数
size_t HPsize(HP* php)
{
	return php->size;
}

（附源码）

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void HpInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

void Hpdestroy(HP* php)
{
	assert(php);
	if (php->arr)
		free(php->arr);
		php->arr = NULL;
	php->capacity = php->size = 0;
}

void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//时间复杂度logn
void AdjustUp(HpDataType* arr,int child)
{
	int parent = (child - 1) / 2;

	while (child>0)
	{
		//if (arr[child] > arr[parent])//升序
		if (arr[child] < arr[parent])//降序
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

void AdjustDown(HpDataType* arr,int parent , int n)
{
	int child = 2 * parent + 1;//左孩子

	while (child < n)
	{
		//if (child + 1 < n && arr[child] > arr[child + 1])//降序
		if (child + 1 < n && arr[child] < arr[child + 1])//升序->建大堆
		{
			child++;
		}
		if (arr[child] > arr[parent])//升序
		//if (arr[child] < arr[parent])//降序
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

void HpPop(HP* php)//出堆：出的是堆顶的数据
{
	assert(php && php->arr);

	swap(&php->arr[0], &php->arr[php->size - 1]);
	--php->size;

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


bool HPEmpty(HP* php)
{
	assert(php);
		return php->size==0;
}

HpDataType HoTop(HP* php)
{
	assert(php && php->size);

	return php->arr[0];
}


void HpPush(HP* php, HpDataType x)
{
	assert(php);
	//扩容
	if (php->capacity == php->size)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HpDataType* tmp = (HpDataType*)realloc(php->arr, newCapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	php->arr[php->size] = x;
	//建小堆
	AdjustUp(php->arr, php->size);
	++php->size;
}

//获取堆中有效数据个数
size_t HPsize(HP* php)
{
	return php->size;
}

相信通过这篇文章你对数据结构（堆）的有了初步的了解。如果此篇文章对你学习数据结构有帮助，期待你的三连，你的支持就是我创作的动力！！！

码农公寓