【初阶数据结构】森林里的树影 “堆” 光：堆

news/2025/2/22 13:25:04

文章目录

  • 1.堆的概念及结构
  • 2.堆的接口实现
    • 2.1 堆的初始化
    • 2.2 堆的销毁
    • 2.3 堆的交换
    • 2.4 堆的向上调整
    • 2.5 堆的插入
    • 2.6 堆的向下调整
    • 2.7 堆的删除
    • 2.8 堆顶获取
    • 2.9 堆的判空
    • 2.10 堆的节点个数
    • 2.11 堆的打印
    • 2.12 堆的排序（向上建堆）
    • 2.13 堆的排序（向下建堆）
  • 3.堆排序效率比较
  • 4.代码展示
    • 4.1 Heap.h
    • 4.2 Heap.c
  • 希望读者们多多三连支持
  • 小编会继续更新
  • 你们的鼓励就是我前进的动力！

初步了解了关于树型结构的知识与结构后，堆的功能实现能帮我们学会一种排序——堆排序，二叉树也是很重要的一种文件式的结构

在学习本专题前，请详细学习有关树的知识与结构

传送门：【初阶数据结构】树型数据的勘探：树(暂未出版)

1.堆的概念及结构

如果有一个关键码的集合 K = { k 0 k_0 k0​， k 1 k_1 k1​， k 2 k_2 k2​，…， k n − 1 k_{n-1} kn−1​}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： K i K_i Ki​ <= K 2 ∗ i + 1 K_{2*i+1} K2∗i+1​ 且 K i K_i Ki​<= K 2 ∗ i + 2 K_{2*i+2} K2∗i+2​ ( K i K_i Ki​ >= K 2 ∗ i + 1 K_{2*i+1} K2∗i+1​ 且 K i K_i Ki​ >= K 2 ∗ i + 2 K_{2*i+2} K2∗i+2​) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆

堆的性质：

🚩堆中某个结点的值总是不大于或不小于其父结点的值

🚩堆总是一棵完全二叉树

堆的结构：

typedef int HPDataType;

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

堆的本质就是一个动态数组，把数组以堆的形式呈现出来而已，所以在实现堆的功能时要多画图来帮助理解

2.堆的接口实现

2.1 堆的初始化

void HeapInit(HP* php)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	php->size = 0;
	php->capacity = 4;
}

熟悉的初始化配方：

  1. 判断是否为空指针
  2. 创建空间，注意是否会因为开辟失败造成空指针
  3. 初始化变量 size 和 capacity

🔥值得注意的是： 参数的指针浅拷贝，指向同一块空间，能够改变该空间里的内容，不涉及改变原空间的地址，所以传一级指针即可

2.2 堆的销毁

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

2.3 堆的交换

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

因为在堆调整中涉及多次的节点交换，所以额外写一个 Swap 交换函数方便使用

2.4 堆的向上调整

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向上调整通常用于最大堆的调整

当向最大堆中插入一个新元素时，新元素会被放置在堆的末尾（即数组的最后一个位置），此时可能会破坏堆的性质（最大堆要求每个节点的值都大于或等于其子节点的值）

通过调用 AdjustUp 函数，可以将新插入的元素上浮到合适的位置，使得整个堆重新满足最大堆的性质

请添加图片描述

🔥值得注意的是：

  1. 无论是左节点还是右节点，父亲节点的索引可以通过 (child - 1) / 2 计算得出
  2. while 循环的条件 child > 0 不能写成 child >= 0。当 child 等于 0 时，表示已经到达堆顶，按照 parent = (child - 1) / 2 计算，(-1) / 2 结果为 0（整数除法向下取整），这会导致 parent 和 child 相等，无法向上调整，陷入类似死循环的效果
  3. 除了 child 这个数据，前面的数据构成堆，因为向上调整的前提是其他数据都成堆

2.5 堆的插入

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity *= 2;
	}

	php->a[php->size] = x;
	AdjustUp(php->a, php->size);
	php->size++;
}

实现了向上调整，那么插入就很容易了，检查容量是否足够插入，调整新插入的数据也构成堆即可

🔥值得注意的是： 不是 php->capacity * 2 ，而是 php->capacity * 2 * sizeof(HPDataType)，注意是字节数不是容量数

2.6 堆的向下调整

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

向下调整通常用于最小堆的调整（这里写的是最大堆的调整）

向下调整的前提是左右子树都必须是大堆或者小堆

请添加图片描述
🔥值得注意的是：

  1. 必须把大的那个孩子往上调，保证大堆的性质
  2. 这里假设子节点中的左孩子 child = parent * 2 + 1 是子节点中最大的
  3. child + 1 < n && a[child + 1] > a[child] 的目的是判断是否存在右子节点，如果存在，再判断左子节点是否大于右子节点，如果大于就交换
  4. 不能写成 a[child + 1] > a[child] && child + 1 < n，要先判断是否存在再访问，不然就非法越界了

2.7 堆的删除

在写堆删除代码前，我们要思考一个问题：

为什么不用像之前顺序表那样常用的删除方法——后一个覆盖前一个？

在这里插入图片描述

比如一个数组 {42，12，18，4，2，3}

如果采用后一个覆盖前一个的方法删除节点：

  1. 向下调整的效率是 O( l o g n log_n logn​) ，后一个覆盖前一个的效率是 O(n) ，假设需要挪动100万次，那么向下调整只需最多20次就能解决，这效率翻得可不止一倍两倍
  2. 后一个覆盖前一个之后父子关系全乱，无法进行堆调整

删除堆通常是删除堆顶的数据，将堆顶的数据和最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法

那么为什么是采用最后一个叶节点和根节点交换？

在这里插入图片描述

画图可以发现这种交换方式，不会太大程度上破坏堆的结构，保证能够进行向下调整来恢复堆的秩序

请添加图片描述

🔥值得注意的是： 删除特定位置元素的方法和删除堆顶是一样的

  1. 遍历整个堆来找到目标元素位置
  2. 将目标位置的元素与堆的最后一个元素进行交换
  3. 根据交换后该元素的值与周围元素的大小关系，决定是进行上浮操作还是下沉操作来恢复堆的性质

因此删除堆的代码也能轻松写出来：

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

2.8 堆顶获取

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

返回堆顶元素的值，最大堆的堆顶元素是堆中的最大值，最小堆的堆顶元素是堆中的最小值

2.9 堆的判空

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

如果 php->size 等于 0，说明堆中没有元素，函数返回 true；否则返回 false

2.10 堆的节点个数

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

设置一个返回 size 的函数方便获取堆的节点个数，否则获取 size 只能通过遍历

2.11 堆的打印

void HeapPrint(HP* php)
{
	int i;
	for (i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

2.12 堆的排序（向上建堆）

既然堆有调整大小顺序的性质，那么就可以据此实现排序的功能

我们知道无论是向上调整，还是向下调整，都要基于一个具有完整性质的堆下来实现，分为向上建堆和向下建堆

向上建堆：

向上建堆的核心思想是逐个插入元素到堆中，每插入一个元素就对其进行向上调整操作，使其满足堆的性质。具体来说，从数组的第一个元素开始，依次将每个元素插入到已经构建好的部分堆中，然后通过上浮操作将该元素调整到合适的位置，确保整个数组始终保持堆的性质。其实就是对堆插入的模拟实现

建好堆之后，就能对堆进行排序，排序分为升序和降序

  • 升序：建大堆
  • 降序：建小堆

为什么排序是这样建堆呢？

在这里插入图片描述

假设我们要实现升序，如果是建小堆的话，最小值就放在最上面不能动了，剩下的数如果想排序那又得看成一个堆，但是这样父子关系全乱了，因此每排好一个数就要重新建堆，那么效率就太低了。

请添加图片描述

实现升序就要考虑建大堆，然后再模拟堆删除的方式，不断把大的值调到最下面，最上面小的值通过向下调整，把堆调整为正常的大堆，保证左右子树都是大堆。此时最大的值又在最顶上，--end，和倒数第二个节点交换，重复上面的操作，循环往复就能实现排序

因此排序的代码为：

void HeapSort(HPDataType* a, int n)
{
	//向上调整建堆,i是下标,n是个数,a是数组 -- O(N * log N)
	for (int i = 0; i < n; ++i)
	{
		AdjustUp(a, i);
	}
	
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		--end;
	}
}

2.13 堆的排序（向下建堆）

向下建堆：

向下建堆的过程可以看作是一种分治策略，将一个大问题分解为多个小问题。向下建堆的核心思想是从最后一个非叶子节点开始，依次对每个非叶子节点进行向下调整（下沉）操作，使得以该节点为根的子树满足堆的性质，最终整个数组构成一个堆。简单来说就是对下面每一个小堆依次调整，最终整体就形成了一个大堆

在这里插入图片描述

假设有个数组{2，1，5，7，6，8，0，9，4，3}，要实现升序建大堆

  1. 先从 6 这个堆开始调整
  2. 然后按数组顺序往前推，调整 7 这个堆
  3. 依次往前推对每个堆调整，最终就建成了一个大堆

建好之后，排序的方法和向上建堆是一样的

因此排序的代码为：

void HeapSort(HPDataType* a, int n)
{
	//向下调整建堆 -- O(N)
    //n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		--end;
	}
}

3.堆排序效率比较

向下建堆：
请添加图片描述
因此：向下建堆的时间复杂度为O(N)

用同样的方法，也能算出向上建堆的时间复杂度为O(N * log N)

所以向下建堆是更高效的

4.代码展示

传送门：Gitee堆代码

4.1 Heap.h

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

typedef int HPDataType;

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

void HeapInit(HP* php);

void HeapDestroy(HP* php);

void Swap(HPDataType* p1, HPDataType* p2);

void AdjustUp(HPDataType* a, int child);

void AdjustDown(HPDataType* a, int n, int parent);

void HeapPush(HP* php, HPDataType x);

void HeapPop(HP* php);

HPDataType HeapTop(HP* php);

bool HeapEmpty(HP* php);

int HeapSize(HP* php);

void HeapPrint(HP* php);

void HeapSort(HPDataType* a, int n);

4.2 Heap.c

#define _CRT_SECURE_NO_WARNINGS

#include "Heap.h"

void HeapInit(HP* php)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	php->size = 0;
	php->capacity = 4;
}

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//除了child这个数据，前面的数据构成堆
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity *= 2;
	}

	php->a[php->size] = x;
	AdjustUp(php->a, php->size);
	php->size++;
}

//左右子树都必须是大堆或者小堆
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

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

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

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

void HeapPrint(HP* php)
{
	int i;
	for (i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

void HeapSort(HPDataType* a, int n)
{
	//向上调整建堆,i是下标，n是个数 -- O(N * log N)
	for (int i = 0; i < n; ++i)
	{
		AdjustUp(a, i);
	}

	/*向下调整建堆 -- O(N)
    n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点*/
	/*for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}*/

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		--end;
	}
}

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！


http://www.niftyadmin.cn/n/5862322.html

相关文章

【时时三省】(C语言基础）求1*2*3*4*5用C语言表示

【时时三省】(C语言基础）求1*2*3*4*5用C语言表示

山不在高&#xff0c;有仙则名。水不在深&#xff0c;有龙则灵。 ----CSDN 时时三省 示例&#xff1a; 输出结果为120
阅读更多...
RTSP场景下RTP协议详解及音视频打包全流程

RTSP场景下RTP协议详解及音视频打包全流程

RTSP场景下RTP协议详解及音视频打包全流程 一、RTSP与RTP的关系 RTSP&#xff1a;负责媒体会话控制&#xff08;DESCRIBE、SETUP、PLAY、PAUSE&#xff09;&#xff0c;通过SDP协商传输参数&#xff08;端口、编码格式、封装模式&#xff09;。RTP&#xff1a;实际传输音视频数…
阅读更多...
ARM Linux V4L2 Camera 实验

ARM Linux V4L2 Camera 实验

使用 ov2640 V4L2 是 Video for linux two 的简称&#xff0c;是 Linux 内核中视频类设备的一套驱动框架&#xff0c;为视频类设备驱动 开发和应用层提供了一套统一的接口规范 使用 V4L2 设备驱动框架注册的设备会在 Linux 系统/dev/目录下生成对应的设备节点文件&#xff0c…
阅读更多...
vxe-table实现动态列

vxe-table实现动态列

vxe-table实现动态列 1.动态列解释2.解决步骤2.1将后端返回的动态列表头&#xff0c;按照格式拼接在固定列表头上2.2将后端返回的列表数据按照键值对格式组装 1.动态列解释 正常列表是有固定的列&#xff1b;我的需求是&#xff0c;最初只知道表格的固定两列&#xff0c;查询数…
阅读更多...
Arcmap和ArcgisPro重装及配置迁移

Arcmap和ArcgisPro重装及配置迁移

近期要重装一下ArcgisPro&#xff0c;在此记录并作为大家的借鉴 1.备份配置文件&#xff1a;其中Desktop10.8为Arcmap的配置文件 2.通过控制面板卸载&#xff0c;arcpro卸载时间较长&#xff0c;先将语言包等卸载&#xff0c;最后再卸载5G主程序&#xff0c;有些文章会介绍清理…
阅读更多...
【Linux专栏】rsync 同步文件时自动创建目录

【Linux专栏】rsync 同步文件时自动创建目录

Linux && Oracle相关文档，希望互相学习，共同进步 风123456789～-CSDN博客 1.背景 rsync 同步文件夹，之前的文章中也写过了(详见：【Linux专栏】find命令+同步 实验-CSDN博客 )，可以同步指定文件夹、或者筛选指定时间范围的文件夹，然后将符合条件的文件夹全部同步…
阅读更多...
【Python爬虫(31)】解锁Python多线程编程：从入门到实战

【Python爬虫(31)】解锁Python多线程编程：从入门到实战

【Python爬虫】专栏简介&#xff1a;本专栏是 Python 爬虫领域的集大成之作&#xff0c;共 100 章节。从 Python 基础语法、爬虫入门知识讲起&#xff0c;深入探讨反爬虫、多线程、分布式等进阶技术。以大量实例为支撑&#xff0c;覆盖网页、图片、音频等各类数据爬取&#xff…
阅读更多...
路由基本配置

路由基本配置

学习目标 • 根据拓扑图进行网络布线。 • 清除启动配置并将路由器重新加载为默认状态。 • 在路由器上执行基本配置任务。 • 配置并激活以太网接口。 • 测试并检验配置。 • 思考网络实施方案并整理成文档。 任务 1&#xff1a;网络布线 使用适当的电缆类型连接网络设备。…
阅读更多...
最新文章

Copyright @ 2022~2023