数据结构与算法：堆

数据结构与算法：堆

    • 堆
      • 堆的定义
      • 堆的实现
        • 结构分析
        • 初始化
        • 向上调整算法
        • 向下调整算法
        • 堆的插入
        • 堆的删除
        • 得到堆顶元素
        • 判断堆是否为空
      • 堆的应用
        • TopK问题

堆

堆的定义

定义：

堆是一种数据结构，本质上是一个特殊的树结构，它是一个完全二叉树，其中每个节点的值都大于等于其子节点的值（对于大堆）或者小于等于其子节点的值（对于小堆）。

根据以上定义，一个数据结构可以称为堆有两个条件：

  • 是一颗完全二叉树
  • 每个父节点的值大于其子节点的值 或 每个父节点的值大于其子节点的值

其中，每个父节点的值大于其子节点的值称为大堆，每个父节点的值小于其子节点的值称为小堆。

以下就是一个大堆：
在这里插入图片描述

由于堆具有一定的规律，所以比一般的二叉树更有实际意义，比如堆排序以及TopK问题。

堆的实现

结构分析

堆一般用顺序表或数组来实现，那么一个树状结构要如何放到线性表或数组中呢？
一般而言，我们的处理方式是对树进行层序遍历，将每一层按顺序放到线性结构中，如下：

请添加图片描述

后续我们的实现堆，也是通过顺序表的结构，因为这一种结构更常见，实际意义也更高。但是在分析问题是，利用树结构会更加直观。

基本结构：

typedef int HPDataType;

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

这段代码定义了一个小堆。下面对每一行代码进行详细解析：

typedef int HPDataType;

这行代码定义了一个名为HPDataType的新类型，它是int类型的别名。这个别名将用于定义堆中的元素的类型，当后续需要用堆存储其它数据类型时，直接在此处修改即可。

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

这行代码定义了一个名为Heap的结构体类型，同时给这个结构体类型起了一个别名HP。Heap结构体包含了三个成员变量：

  • a是指向HPDataType类型的指针，它将用于存储堆的元素。
  • size表示当前堆中的元素个数。
  • capacity表示堆的最大容量，即可以容纳的元素个数的上限。

这个结构体定义了一个数据结构，其中元素的类型为HPDataType。

综上所述，这段代码定义了一个名为HP的最小堆数据结构，其中堆的元素类型为HPDataType，堆的元素存储在数组a中，堆的当前元素个数存储在size中，堆的最大容量存储在capacity中。

初始化
//初始化
void HeapInit(HP* php)
{
	assert(php);

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

这段代码定义了一个名为HeapInit的函数，该函数的参数是一个指向HP类型的指针。

函数开始使用assert宏来确保传入的指针不为空，如果为空则会终止程序运行。

接着，函数通过指针php来访问HP结构体的成员变量。

首先，将php->a设置为NULL，表示堆中的元素数组为空。

然后，将php->size设置为0，表示堆中当前元素个数为0。

最后，将php->capacity设置为0，表示堆的容量为0，意味着还没有分配内存空间。

因此，这段代码的作用是初始化一个堆，将堆的元素数组指针设为NULL，元素个数和容量都设为0。这种初始状态的堆是一个空堆，没有任何元素。

在讲解堆的其它操作之前，要先讲解堆的最重要的两个算法，这两个算法可以维持堆的有序性。

向上调整算法

现在假设我有以下堆结构：
在这里插入图片描述

我现在在堆尾部插入一个数据，如何将数据调整到合适的位置，保证这个结构依然满足堆的要求？
在这里插入图片描述
想要将其插入到指定位置，就要使用到向上调整算法：将最后一个节点向上调整到合适的位置。

首先讲解一个公式：堆结构中父节点与子节点的下标关系

假设父节点的下标为parent，则其左子节点的下标为 2 * parent+1，右子节点的下标为 2 * parent+2。

由于大堆要保证每隔父亲节点大于两个子节点，而除去最后一个节点，其它的节点已经满足堆结构了，所以此处需要将最后一个节点不断地与其父亲节点比较，如果其比父亲节点大，就交换位置，然后继续和新的父亲节点比较，直到比当前的父亲节点小，或者到达堆顶为止。

图示：
请添加图片描述

在顺序表中的效果（实际效果）：
请添加图片描述

代码实现：

//向上调整
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;
		}
	}
}

代码详解：

  1. 函数定义：
void AdjustUp(HPDataType* a, int child)

该函数接受两个参数：指向数组的指针a和待调整元素的索引child。HPDataType是堆中存储的元素类型。

  1. 定义父节点索引：
int parent = (child - 1) / 2;

根据完全二叉树的性质，节点i的父节点索引是(i - 1) / 2，所以计算出child节点的父节点索引。

  1. 进入循环：
while (child > 0)

当child大于0时，继续执行循环。循环的目的是将child节点与其父节点进行比较，并根据需要进行交换。

  1. 比较child节点与其父节点的大小：
if (a[child] < a[parent])

如果child节点的值小于其父节点的值，说明需要进行交换。这是一个小堆的向上调整操作。如果想要实现大堆的向上调整，需要将判断条件改为>。

  1. 交换节点值和更新索引：
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;

交换child节点和父节点的值，然后更新child和parent的值，使其指向交换后的节点。

  1. 循环结束：
else
{
    break;
}

如果child节点大于等于其父节点，说明调整完成，跳出循环。

通过这个向上调整的操作，可以将新插入的元素调整到合适的位置，以保证堆的性质。

向下调整算法

如果堆中某个节点的值被修改，如何调整这个堆的结构保证其依然满足堆的要求？

当堆中的某个节点的值发生改变时（例如，该节点的值被修改），需要进行向下调整操作来保持堆的性质。

向下调整的基本思想是将当前节点与其子节点进行比较，并根据堆的类型（大堆或小堆）选择合适的交换操作。如果当前节点的值小于（或大于）其子节点的值，那么需要将当前节点与其子节点中的较大（或较小）值进行交换。然后，继续向下调整交换后的子节点，直到满足堆的性质为止。

示意图如下：
请添加图片描述在顺序表中的效果（实际效果）：
请添加图片描述

代码如下：

//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;

	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

函数AdjustDown的参数包括一个整型数组a，数组大小size，以及一个表示待调整节点的下标parent。

首先，计算待调整节点的左子节点下标child = parent * 2 + 1。

然后，进入一个循环，判断child是否越界。如果child < size，则说明待调整节点有左子节点。

在循环中，首先判断是否存在右子节点，并且右子节点的值大于左子节点的值，如果满足这个条件，则将child更新为右子节点的下标。

接下来，判断child节点的值是否大于parent节点的值。如果满足这个条件，则交换child和parent节点的值，并更新parent为child，再次计算child的值。

如果child节点的值不大于parent节点的值，则退出循环。

函数结束后，即可保证以parent节点为根的子树满足堆的性质。

堆的插入

为了不破坏堆的结构，我们一般会在堆的末尾插入节点，当插入完节点后，还要将这个节点放到合适的为止，那么此时就需要使用到向上调整算法将此节点调整到合适的位置。

比如这样：
请添加图片描述
但是由于我们的堆结构是基于顺序表实现的，在插入最后一个元素时，还要考虑是否空间充足，从而判断是否需要扩容。

代码如下：

//插入
void HeapPush(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->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

具体解释如下：

  1. 首先，使用assert宏确保传入的二叉堆指针php不为空。
  1. 如果二叉堆已满（即php->size等于php->capacity），则需要扩容。这里使用了realloc函数重新分配内存空间，新的容量为原容量的两倍。如果realloc失败，则打印错误信息并退出程序。分配成功后，将新的空间地址保存在tmp指针中。
  1. 将tmp指针赋值给php->a，即将php->a指向新的内存空间。
  1. 将新插入的元素x赋值给php->a的最后一个位置，即php->a[php->size]。然后，将php->size加1，表示堆的大小增加。
  1. 调用AdjustUp函数，对刚插入的元素进行向上调整（上浮操作），以保持二叉堆的性质。具体来说，就是将x与其父节点比较并交换，直到x不再比其父节点小或者已经到达堆顶位置。
堆的删除

堆的删除要求必须删除堆顶，这样做的意义是每次都可以取出堆的最大值或最小值。
要注意，当堆顶是最大值时，最后一个节点不一定是最小值（对于大堆）。
在这里插入图片描述
比如这个堆结构中，最大值是第一个节点，而最小值不是最后一个节点。

那么如何直接删掉最顶上的节点呢？删掉节点后又要如何保证这个堆符合要求呢？
对于这个问题，我们采取的方法是：

将第一个节点与最后一个节点交换
然后删除尾部节点（即被交换前的第一个节点）
将堆顶节点（即交换前的最后一个节点）向下调整

示意图如下：
请添加图片描述
代码实现：

//删除
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;//删除尾节点

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

以下是对代码的详细解释：

  1. 首先，代码使用断言来确保传入的堆指针 php 不为空，并且堆的大小 php->size 大于 0。
  1. 接下来，代码调用 Swap 函数来交换根节点 php->a[0] 和最后一个节点 php->a[php->size - 1] 的值。这样就将堆顶的元素移动到最后。
  1. 然后，代码将堆的大小减一，表示删除了一个节点。
  1. 最后，代码调用 AdjustDown 函数将交换后的根节点下沉到合适的位置，以保持堆的特性。

通过这些步骤，HeapPop 函数完成了从堆中删除根节点的操作，并且保持了堆的特性。

得到堆顶元素

想要得到堆顶的元素，其实就是拿到a[0]。

//返回堆顶
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

过于简单，不做解释了。

判断堆是否为空

判断堆是否为空，即判断size是不是0。
代码如下：

//判空
bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

堆的应用

有了以上接口，我们现在就利用堆来实现一些具体功能：

TopK问题

所谓TopK问题，就是在一串数据中，找到最大的K个数字。
那么我们要如何实现这样功能呢？
不少人会想到，将整个数组转化为一个大堆，然后取出堆中最前面的k个节点值，这个方法很好想，但是建堆的复杂度可不低，而且将一个数组转化为一个堆，那为什么不直接对这个数组排序？

不妨想想，我们的目的只是取出最大的k个数字，我们可以用一块空间来存储最大的k个数字。接着遍历这个数组，将目前最大的K个数字存在这个空间中，最后我们只需要遍历一次数组，就可以取出最大的K个数字了。

对于这个用于存储最大的K个数据的空间，我们要保证每次都拿出最大的K个数据中最小的1个节点去和后续的值比较，只要一个数据可以比之前数据的最大的K个数据中最小的那个数字大，那么它就可以进入当前的TopK。

那么我们要如何维护这样的一个空间，保证每次都可以取出最小的那个值呢？
答案是建一个小堆，为什么是小堆？
因为小堆的堆顶就是这个堆中最小的数字，在对比后续数值时，将其与当前的堆顶对比即可。

整体思路如下：

  • 取出数据的前K个数值，创建一个K个数的小堆
  • 遍历剩余数据，将每个数据与堆顶比较，如果比堆顶大，就替换掉堆顶
  • 当堆顶被替换后，为了保证堆的结构，对堆顶向下调整到合适位置。

建堆
那么要如何创建一个K个数字的小堆？
假设我们已经创建了一个可以放K个数据的数组minheap[]以及被查找的数组a[]。

我们只需要每次都把数据放到minheap[]的末尾，然后将尾部向上调整到指定位置即可：

	for (int i = 0; i < k; i++)
	{
		minheap[i] = a[i];
		AdjustUp(minheap, i);
	}

图示如下：
请添加图片描述
这个过程中，我们建立了一个有11个元素的堆，每次插入一个值，都将其向上调整到合适的位置。

将后续数值与节点的最小值比较
我们先前已经把数组a[]中的前K个数据取出来了，接下来就要将剩下的size-k个数据一一与堆顶比较。一旦其比当前的堆顶大，就将其向下调整到指定位置，保证堆顶依然是目前的TopK的最小值。

代码如下：

	for (int i = k; i < size; i++)
	{
		if (a[i] > minheap[0])
		{
			minheap[0] = a[i];
			AdjustDown(minheap, k, 0);
		}
	}

总代码如下：

void PrintTopK(int* a, int size, int k)
{
	//------------------------------
	//建立一个k个数字的小堆
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		minheap[i] = a[i];
		AdjustUp(minheap, i);
	}

	//-------------------------------
	//将后续数字与当前的堆中数据比较
	for (int i = k; i < size; i++)
	{
		if (a[i] > minheap[0])
		{
			minheap[0] = a[i];
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");
}

通过这样的一个算法，我们可以只遍历一次数组，就可以将数组中的最大的K个值取出来。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/313582.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

k8s中的基础概念

k8s中的基础概念

k8s可以从硬件和软件两方面来理解&#xff1a; 硬件&#xff1a; 1、节点&#xff08;Node&#xff09;&#xff1a;类似于手机、平板、电脑 2、集群&#xff08;Cluster&#xff09;&#xff1a;多个节点组合到一起 3、持久卷&#xff08;Persistent Volumes&#xff09;&…
阅读更多...
几款优秀科学开源计算软件介绍

几款优秀科学开源计算软件介绍

有一些比较优秀的软件&#xff0c;它们在科学计算、数据处理和分析方面具有广泛的应用和功能。以下是一些比较知名的软件&#xff1a; SciPy&#xff1a;SciPy是一个非常流行的科学计算库&#xff0c;提供了大量的数学函数和算法&#xff0c;用于解决各种科学问题。它支持多种操…
阅读更多...
【实用技巧】Steam Wallpaper Engine 壁纸引擎向手机导入壁纸方法

【实用技巧】Steam Wallpaper Engine 壁纸引擎向手机导入壁纸方法

一、内容简介 本文介绍如何使用电脑上的 Wallpaper Engine &#xff08;Steam 平台中的壁纸引擎&#xff09;向安卓手机导入并使用壁纸。 二、所需原材料 安卓手机&#xff08;以笔者使用的华为荣耀50为例&#xff09;、安装有Steam以及Wallpaper Engine的电脑 三、导入方法…
阅读更多...
清水模板厂家专供 — 易脱模，不翘曲

清水模板厂家专供 — 易脱模，不翘曲

在现代建筑施工中&#xff0c;清水模板的选择对于实现优质建筑表面尤为关键。我们专供的清水模板&#xff0c;凭借其易脱模和不翘曲的特性&#xff0c;为建筑项目提供了理想的解决方案。 产品特点 易脱模性能&#xff1a;我们的清水模板表面光滑细腻&#xff0c;经过特殊处理…
阅读更多...
C++系列-第1章顺序结构-7-浮点型

C++系列-第1章顺序结构-7-浮点型

在线练习&#xff1a; http://noi.openjudge.cn/ https://www.luogu.com.cn/ 总结 本文是C系列博客&#xff0c;主要讲述浮点型的用法 浮点型 1、常量 圆周率是一个常数。计算机程序设计中有一个类似的概念是“常量”。C语言规定&#xff0c;一个常量可以直接调用(如 124、…
阅读更多...
visual studio 出现以下错误: 无法创建网站“ftp://www.8888.com/doc”。未安装与 FTP 服务器进行通信所需的组件。

visual studio 出现以下错误: 无法创建网站“ftp://www.8888.com/doc”。未安装与 FTP 服务器进行通信所需的组件。

上述文件安装一边就可以了
阅读更多...
linux后台进程的总结

linux后台进程的总结

文章目录 方案1 nohup &方案2 screen 方案1 nohup & 1、单独使用 nohup 执行脚本&#xff0c;如下图所示&#xff0c;终端会被接管&#xff0c;就是标准输入stdin 被关闭了&#xff0c;使用ctrlc会导致终止执行&#xff0c;但是可以关闭这个终端&#xff0c;重新打开终…
阅读更多...
GVM垃圾收集算法

GVM垃圾收集算法

分代收集理论 目前主流JVM虚拟机中的垃圾收集器&#xff0c;都遵循分代收集理论&#xff1a; 弱分代&#xff1a;绝大多数对象都是朝生夕灭强分带&#xff1a;经历越多次垃圾收集过程的对象&#xff0c;越难以回收&#xff0c;难以消亡 按照分代收集理论设计的“分代垃圾收集…
阅读更多...
挑选全身动作捕捉设备需要看哪几点？

挑选全身动作捕捉设备需要看哪几点？

随着数字化发展&#xff0c;虚拟数字人成为企业、品牌营销中不可或缺的一环&#xff0c;虚拟数字人可以通过全身动作捕捉设备&#xff0c;能够打破次元壁与用户实时互动。那要怎么挑选全身动作捕捉设备呢&#xff1f; 广州虚拟动力推出了旗舰版惯性动捕设备DreamsCap X1&#…
阅读更多...
洗地机是智商税吗？2024洗地机品牌推荐

洗地机是智商税吗？2024洗地机品牌推荐

为了更加便捷地应对家务&#xff0c;人们一直在不断发明各种工具。从最早的扫把和拖布&#xff0c;到后来的吸尘器和扫地机器人&#xff0c;我们的家务清洁方式不断演进。然而&#xff0c;在最近几年&#xff0c;洗地机的出现彻底改变了我们的家庭清洁体验&#xff0c;为我们带…
阅读更多...
微服务自动化docker-compose

微服务自动化docker-compose

一、docker-compose介绍 Docker Compose是一个用来定义和运行多个复杂应用的Docker编排工具。例如&#xff0c;一个使用Docker容器的微服务项目&#xff0c;通常由多个容器应用组成。那么部署时如何快速启动各个微服务呢&#xff0c;一个个手动启动&#xff1f;假如有上百个微服…
阅读更多...
安卓(雷电)模拟器清除屏幕密码[亲测可用]

安卓(雷电)模拟器清除屏幕密码[亲测可用]

1、设置磁盘可写 启动模拟器&#xff0c;然后在模拟器的设置界面&#xff0c;设置磁盘共享为可写入&#xff0c;重启模拟器&#xff0c;如下图&#xff1a; 2、找到模拟器目录 返回桌面&#xff0c;右键模拟器图标&#xff0c;打开文件所在目录&#xff0c;如下图&#xff1a…
阅读更多...
一天一个设计模式---适配器模式

一天一个设计模式---适配器模式

概念 适配器模式是一种结构型设计模式&#xff0c;用于将一个类的接口转换成客户端所期望的另一个接口。它允许不兼容的接口之间进行协同工作&#xff0c;使得原本由于接口不匹配而无法合作的类能够一起工作。 具体内容 适配器模式主要包括以下几个要素&#xff1a; 目标接…
阅读更多...
Maven_下载_安装_配置

Maven_下载_安装_配置

文章参考&#xff1a;https://zhuanlan.zhihu.com/p/615382243 Maven简介 Maven 是 Apache 软件基金会的一个开源项目,是一个优秀的项目构建工具,它用来帮助开发者管理项目中的 jar,以及 jar 之间的依赖关系、完成项目的编译、测试、打包和发布等工作。 maven优点&#xff1a;…
阅读更多...
呼吸道病毒感染后，为何会引发细菌性肺炎？气道和肠道微生物组改变是关键

呼吸道病毒感染后，为何会引发细菌性肺炎？气道和肠道微生物组改变是关键

谷禾健康 病毒-细菌合并或继发感染 引起呼吸道感染的病毒是导致全世界高发病率和死亡率的原因&#xff0c;数十年来通常发生在冬季。在冬天&#xff0c;空气干燥&#xff0c;那些可能含有病毒的飞沫可以在空气中停留更长时间&#xff0c;并可以进一步传播。此外人的免疫力在冬季…
阅读更多...
[Markdown] Markdown常用快捷键分类汇总

[Markdown] Markdown常用快捷键分类汇总

文章目录 Markdown1、标题2、列表3、强调4、链接和图片5、代码和公式6、表格和任务列表7、引用8、分割线9、脚注10、目录11、注释12、定义 Markdown Markdown是一种轻量级的标记语言&#xff0c;可以让你用简单的语法来编写格式丰富的文档。 Markdown编辑器是一种专门用于编辑…
阅读更多...
连接打印机显示“0x0000011b”错误代码，亲测有效的解决办法

连接打印机显示“0x0000011b”错误代码，亲测有效的解决办法

程序代码园发文地址&#xff1a;null小说,Java,HTML,Java小工具,程序代码园,http://www.byqws.com/ ,连接打印机显示“0x0000011b”错误代码&#xff0c;亲测有效的解决办法http://www.byqws.com/blog/2142.html 最近办公室共享打印机突然打印不了&#xff0c;把之前连接的打印…
阅读更多...
数字图像线性滤波——方框、均值、高斯滤波及opencv（C++）实现示例

数字图像线性滤波——方框、均值、高斯滤波及opencv（C++）实现示例

数字图像线性滤波——方框、均值、高斯滤波及opencv&#xff08;C&#xff09;实现示例 一、图像滤波概念简介二、方框滤波及opencv实现示例1、方框滤波的公式2、opencv方框滤波boxfilter()函数&#xff08;1&#xff09;函数介绍&#xff08;2&#xff09;opencv实现实例&…
阅读更多...
怎样创建vue项目(分别基于vue-cli和vite两种的创建方式)

怎样创建vue项目(分别基于vue-cli和vite两种的创建方式)

一、基于vue-cli脚手架创建 1、安装node.js 1、首先需要安装node.js&#xff0c;推荐下载地址&#xff1a;Node.js 2、检查是否安装成功&#xff0c;使用打开黑窗口的快捷键windowR&#xff0c;输入cmd&#xff0c;在黑窗口输入node -v&#xff0c;如果输出版本号&#xff0…
阅读更多...
LeNet-5（用于手写体字符识别）

LeNet-5（用于手写体字符识别）

结构&#xff1a;输入的二维图像&#xff0c;先经过两次卷积层到池化层&#xff0c;再经过全连接层&#xff0c;最后使用softmax分类作为输出层 每层有多个Feature Map&#xff08;每个Feature Map有多个神经元&#xff09; Feature Map通过一种卷积滤波器提取输入的一种特征 …
阅读更多...
最新文章

Copyright @ 2022~2023