当前位置： 首页 > article >正文

【落羽的落羽 数据结构篇】顺序结构的二叉树——堆

article 2025/2/24 17:12:41

在这里插入图片描述

文章目录

  • 一、堆
    • 1. 概念与分类
    • 2. 结构与性质
    • 3. 入堆
    • 4. 出堆
  • 二、堆排序
  • 三、堆排序的应用——TOP-K问题

一、堆

1. 概念与分类

上一期我们提到，二叉树的实现既可以用顺序结构，也可以用链式结构。本篇我们来学习顺序结构的二叉树，起个新名字——堆（heap）。
堆是完全二叉树，它的底层是顺序结构的数组，具有二叉树特性的同时，还有一些其他性质：

堆分为大堆和小堆（或称为大根堆、小根堆）：

  • 大堆：大堆的每个结点的存储值都 >= 它的子结点的存储值。
  • 小堆：小堆的每个结点的存储值都 <= 它的子结点的存储值。

在这里插入图片描述

譬如，在一个大堆中，某一个父结点的值为20，则它的子结点的值一定<=20；在一个小堆中，某一个父结点的值为20，则它的子结点的值一定>=20。
左孩子和右孩子的值的大小关系不确定。

换句话说，一个堆一定是大堆或小堆。以下的二叉树，既不是大堆也不是小堆，它们就不是堆：在这里插入图片描述

2. 结构与性质

定义数据结构堆：

typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}HP;

上面的画图是用逻辑结构表示堆，用存储结构表示堆就要用到数组了，牢记二叉树结点的编号方式：从上到下，从左到右：在这里插入图片描述
不难推断，堆的数组中有下列性质：

  • 大堆的首元素（根结点）是整个堆的最大值，小堆的首元素（根结点）是整个堆的最小值。
  • 若子结点的下标为i，则它的父结点是(i-1)/2。
  • 若父结点的下标为i，则它的左孩子是2i+1，右孩子是2i+2。结点个数是n，2i+1 >= n 说明无左孩子，2i+2 >= n 说明无右孩子。

顺带给出堆的初始化和销毁方法，以及后面要用到的交换两个变量值的方法：

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

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

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

在这里插入图片描述

3. 入堆

想要把一个新的数据插入堆，分为两步：

  1. 把它插入堆数组末尾
  2. 仅仅插入数据后，可能会破坏堆的性质，所以还要进行“向上调整”操作：将新插入结点顺着其双亲往上调整位置至满足大堆或小堆的位置。
    我们以下面一个小堆为例，插入一个新数据10，如果它小于其父结点（不符合小堆），两者交换。再和新父结点比较，如果小于交换……直到满足小堆：在这里插入图片描述

所以，我们要知道向上调整算法：它有两个参数：要被调整的堆数组，要调整位置的结点的下标：

void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2; //找这个结点的父结点
	while (child > 0)
	{
		//调整的是小堆:  <
		//调整的是大堆:  >
 		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else //新数据已经到了对的位置
		{
			break;
		}
	}
}

这样，我们就能实现入堆操作了：

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity) //空间不够则需增容
	{
		int newcapacity = php->capacity == 0 ? 5 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("relloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x; //新数据插到末尾，即下标为size的位置
	AdjustUp(php->arr, php->size);
	php->size++;
}

测试：
我们来实现一个小堆，乱序给一些数：
在这里插入图片描述

将打印结果排列成堆的逻辑结构看看，发现确实是正确的小堆：在这里插入图片描述

4. 出堆

我们所谓的出堆，出的并不是数组末尾数据，出的是第一个数据——堆的根结点。但是，直接除去数组首元素，再将后面元素的下标全体前挪，会使堆的所有结点位置关系“大乱套”，再想调整可就麻烦了。
因此，我们选择这样的出堆定元素方法：先将堆顶数据和堆的最后一个数据交换，size- -把数组末尾数据出掉，再对堆顶元素进行“向下调整”操作。相比刚才所有结点位置大乱套，这样只要调整一个结点的位置就好了。

向下调整算法和向上调整类似：它是比较结点和其较大或较小孩子的值，不断往下交换调整位置直至满足大堆或小堆：在这里插入图片描述

向下调整算法有三个参数：要被调整的堆数组、要调整的结点的下标、堆的数据个数

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]) //找两个孩子中的较大/较小者
		{
			child++;
		}

		//调整的是小堆:  <
		//调整的是大堆:  >
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else //调整完成
		{
			break;
		}
	}
}

这样，我们就能实现出堆操作了：

void HPPop(HP* php)
{
	assert(php);
	assert(php->size != 0); //堆不能为空，否则无数据可出
	Swap(&php->arr[0], &php->arr[php->size - 1]); //交换堆顶和堆尾数据
	php->size--; //将堆尾数据出掉
	AdjustDown(php->arr, 0, php->size);
}

测试：
我们来实现一个大堆，乱序给一些数，再进行一次出堆：
在这里插入图片描述

分析逻辑结构，可以看到大堆实现成功，出堆也没有问题：在这里插入图片描述

在这里插入图片描述

二、堆排序

堆排序是一种排序方法，不是借助堆的数据结构，而是利用堆的思想进行排序：
一个n个元素的数组，假如想排升序，就将数组建成一个大堆，堆顶是最大值，将堆顶和堆尾交换，下标n-1处就是最大值了；我们再把前n-1个数据调整成大堆，此时堆顶就是第二大的数据，堆顶和堆尾交换，下标n-2处就是第二大值了……直至排序完成。

相反地，想排成降序就建小堆，道理是一样的，我们下面就以建成大堆为例。

堆排序的关键在于一开始建堆的方法，可以分为向下调整建堆和向上调整建堆：

void HPCreat_Down(int* arr, int n) //向下调整算法建堆
{
	//从尾结点的父结点开始往上遍历，每一个结点都进行向下调整
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n); 
	}
}

void HPCreat_Up(int* arr, int n) //向上调整算法建堆
{
	//从第一个结点开始往下遍历，每一个结点都进行向上调整
	for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}
}

//注：建的是大堆还是小堆，取决于AdjustUp和AdjustDown函数中的大于还是小于号，上面提到过

知道了建堆方式后，就能实现堆排序了：

void HeapSort(int* arr, int n)
{
	HPCreat_Down(arr, n);
	//或HPCreat_Up(arr, n);
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end); //对新堆顶进行向下调整，以保证堆的性质
		end--;
	}
}

测试：
在这里插入图片描述
很顺利。

关于两种建堆方式的时间复杂度：
推导需要用到数列相关定理公式，我就不再证明了，可以直接记住结果：

  • 向下调整建堆：T(n) = n - log2(n+1)，O(n)
  • 向上调整建堆：T(n) = (n+1) [log2(n+1) - 2] + 2，O(n*logn)

可见，向下调整建堆算法更好一些。

在这里插入图片描述

三、堆排序的应用——TOP-K问题

TOP-K问题，即求n个数据中前K个最大值或最小值，一般情况下n都很大且n >> k。
我们能想到的最简单的方法就是排序了，但是如果数据量太大，数据不能一下子全部加载到内存中，排序就不可取了。最佳的方式就是用堆来解决，思路为：

  • 取前k个数据建堆，遍历剩下的n-k个数据跟堆顶比较。
  • 如果找的是前k个最大值，就建小堆。若第k+1个数比堆顶大，就用它替换堆顶，再调整堆，再比较第k+2个数和堆顶……遍历完，最后堆中的k个数就是n个数里面前的k个最大值了。
  • 如果找的是前k个最小值，就建大堆。若第k+1个数比堆顶小，就用它替换堆顶，再调整堆，再比较第k+2个数和堆顶……遍历完，最后堆中的k个数就是n个数里面前的k个最小值了。

应该很好理解吧。

举个栗子，我先来造十万个数据，保存到一个文本文件data.txt中

void CreatData()
{
	srand(time(0));
	FILE* file = fopen("data.txt", "w");
	if (file == NULL)
	{
		perror("fopen fail!");
		exit(2);
	}
	for (int i = 0; i < 100000; i++)
	{
		int x = (rand() + i) % 100000 + 1;
		fprintf(file, "%d\n", x);
	}
	fclose(file);
}

在这里插入图片描述

最后来实现TOP_K算法（以找前k个最小值为例）：

void Top_K()
{
	int k;
	printf("请输入K:");
	scanf("%d", &k);
	FILE* file = fopen("data.txt", "r");
	if (file == NULL)
	{
		perror("fopen fail!");
		exit(2);
	}

	int* maxHeap = (int*)malloc(sizeof(int) * k);
	if (maxHeap == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	for (int i = 0; i < k; i++)
	{
		//先将前k个数存到maxHeap中
		fscanf(file, "%d", &maxHeap[i]);
	}
	
	HPCreat_Down(maxHeap, k); //找前k个最小值，建大堆

	//遍历剩下的数
	int x;
	while (fscanf(file, "%d", &x) != EOF) //fscanf文件读取结束会返回EOF
	{
		//谁小谁当堆顶
		if (x < maxHeap[0])
		{
			maxHeap[0] = x;
			AdjustDown(maxHeap, 0, k);
		}
	}	
	fclose(file);

	//处理完成，打印结果
	for (int i = 0; i < k; i++)
	{
		printf("%d ", maxHeap[i]);
	}
}

测试：
在这里插入图片描述

可以看到，每次输入一个k，都能找到前k个最小值，只不过不是按大小顺序输出的。顺带一提，这个算法的时间复杂度O(n) = k + (n - k)log2k
在这里插入图片描述

本篇完，感谢阅读


http://www.kler.cn/a/559185.html

相关文章：

  • DAY11 Tensorflow 鸢尾花数据集可视化训练
  • MobaXterm_Portable_v23.2 免费下载与使用教程（附安卓替代方案）
  • Java中的自然语言处理（NLP）工具：Stanford NLP、Apache OpenNLP、DL4J
  • 萌新学 Python 之 lambda 函数
  • 财务运营域——营收稽核系统设计
  • springcloud gateway并发量多大
  • 蓝桥杯训练 补题
  • 2025年微店平台商品详情接口调用指南（Python代码示例）
  • [LeetCode力扣hot100]-快速选择和快排
  • DeepSeek各模型现有版本对比分析
  • 深入解析 Spring WebFlux：原理与应用
  • 2025年SCI一区智能优化算法：混沌进化优化算法（Chaotic Evolution Optimization, CEO），提供MATLAB代码
  • 下载CentOS 10
  • Debian系统终端输入ifconfig报错
  • 深度学习-7.超参数优化
  • 设计模式教程：中介者模式（Mediator Pattern）
  • AxiosError: Network Error
  • Ubuntu服务器 /data 盘需要手动挂载的解决方案
  • 机器视觉3D中，深度图转点云图精度损失分析
  • 基于spring boot物流管理系统设计与实现(代码+数据库+LW)