数据结构与算法：堆

数据结构与算法：堆

    • 堆
      • 堆的定义
      • 堆的实现
        • 结构分析
        • 初始化
        • 向上调整算法
        • 向下调整算法
        • 堆的插入
        • 堆的删除
        • 得到堆顶元素
        • 判断堆是否为空
      • 堆的应用
        • 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个值取出来。

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Qt - QML框架

Qt - QML框架

文章目录 1 . 前言2 . 框架生成3 . 框架解析3.1 qml.pro解析3.2 main.cpp解析3.3 main.qml解析 4 . 总结 【极客技术传送门】 : https://blog.csdn.net/Engineer_LU/article/details/135149485 1 . 前言 什么是QML&#xff1f; QML是一种用户界面规范和编程语言。它允许开发人员…
阅读更多...
Invalid bound statement(只有调用IService接口这一层会报错的)

Invalid bound statement(只有调用IService接口这一层会报错的)

问题描述:controller直接调用实现类可以,但是一旦调用IService这个接口这一层就报错. 找遍了大家都说是xml没对应好,但是我确实都可以一路往下跳,真的对应好了.结果发现是 MapperScan写错了,如下才是对的. MapperScan的作用是不需要在mapper上一直写注解了,只要启动类上写好就放…
阅读更多...
python 计数器

python 计数器

这个Python脚本定义了一个名为new_counter()的函数&#xff0c;它读取系统时间并将其与存储在文件中的时间进行比较。然后根据比较结果更新存储在另一个文件中的计数器值。如果系统时间与存储的时间匹配&#xff0c;则计数器值增加1。如果系统时间与存储的时间不匹配&#xff0…
阅读更多...
C#实现Excel合并单元格数据导入数据集

C#实现Excel合并单元格数据导入数据集

目录 功能需求 Excel与DataSet的映射关系 范例运行环境 Excel DCOM 配置 设计实现 组件库引入 ​方法设计 返回值 参数设计 打开数据源并计算Sheets 拆分合并的单元格 创建DataTable 将单元格数据写入DataTable 总结 功能需求 将Excel里的worksheet表格导入到Da…
阅读更多...
MySQL连续案例续集

MySQL连续案例续集

1、查询学过「张三」老师授课的同学的信息 分析&#xff1a;平均 avg&#xff1a;GROUP BY分组 从高到低&#xff1a;ORDER BY 所有学生的所有课程的成绩&#xff1a;行转列 所有学生----外联&#xff08;所有&#xff09;&#xff1a;RIGHT JOIN右联 SELECTs.*,c.cname,t.tnam…
阅读更多...
PPT自动化处理

PPT自动化处理

python-pptx模块 可以创建、修改PPT(.pptx)文件非Python标准模块&#xff0c;需要单独安装 在线安装方式 pip install python-pptx 读取slide幻灯片 .slides 获取shape形状 slide.shapes 判断一个shape中是否存在文字 shape.has_text_frame 获取文字框 shape.text_f…
阅读更多...
可以打印试卷的软件有哪些？推荐这几款

可以打印试卷的软件有哪些？推荐这几款

可以打印试卷的软件有哪些&#xff1f;随着科技的飞速发展&#xff0c;越来越多的学习工具如雨后春笋般涌现&#xff0c;其中&#xff0c;能够打印试卷的软件尤其受到广大学生和家长的青睐。这些软件不仅方便快捷&#xff0c;而且内容丰富&#xff0c;可以满足不同学科、不同年…
阅读更多...
简单明了，汽车级LM317系列LM317D2TR4G线性电压稳压器电源设计-参数应用方案分享

简单明了，汽车级LM317系列LM317D2TR4G线性电压稳压器电源设计-参数应用方案分享

低压差线性稳压器&#xff08;LDO&#xff09;&#xff0c;是指一种具有恒定电流输出电压的装置&#xff0c;主要由输入变压器、整流器、输出变压器三部分构成&#xff0c;工业原理为将输入的交流电压经过整流、滤波后得到直流输出电压&#xff0c;再经过控制元件和开关器件将稳…
阅读更多...
协作共生：数字孪生与智慧城市的共赢之路

协作共生：数字孪生与智慧城市的共赢之路

引言 随着科技的飞速发展&#xff0c;数字孪生和智慧城市的概念逐渐融入现代城市的规划和建设中。数字孪生技术为智慧城市的建设提供了强大的支持&#xff0c;而智慧城市则为数字孪生的应用提供了广阔的舞台。本文将深入探讨数字孪生与智慧城市之间的相互影响与协作&#xff0…
阅读更多...
使用Nginx作为反向代理服务器在Linux中的最佳实践

使用Nginx作为反向代理服务器在Linux中的最佳实践

在Linux环境下&#xff0c;Nginx因其高效性能、稳定性以及丰富的功能集而广泛用于作为反向代理服务器。以下是在Linux中使用Nginx作为反向代理服务器的最佳实践&#xff1a; 1. 安装与配置 首先&#xff0c;确保你的Linux发行版已经安装了Nginx。大多数Linux发行版都提供了Ng…
阅读更多...
分布式系统架构设计之分布式缓存技术选型

分布式系统架构设计之分布式缓存技术选型

一、概述 随着互联网业务的快速发展&#xff0c;分布式系统已经成为了解决大规模并发请求、高可用性、可扩展性等问题的重要手段。在分布式系统中&#xff0c;缓存作为提高系统性能的关键技术&#xff0c;能够显著降低数据库负载、减少网络延迟、提高数据访问速度。当面对大量…
阅读更多...
【局域网window10系统搭建共享文件夹或与手机共享】

【局域网window10系统搭建共享文件夹或与手机共享】

局域网window10系统搭建共享文件夹或与手机共享 1、Window 10之间搭建共享文件夹1.1 ping通两台window 10 电脑1.2 创建共享账号&#xff08;window 10专业版&#xff09;1.3 创建共享文件夹以及配置1.4访问共享文件夹 2、手机访问window10 共享文件夹&#xff08;结合步骤一&a…
阅读更多...
Python 网络数据采集（四）：Selenium 自动化

Python 网络数据采集（四）：Selenium 自动化

Python 网络数据采集&#xff08;四&#xff09;&#xff1a;Selenium 自动化 前言一、背景知识Selenium 4Selenium WebDriver 二、Selenium WebDriver 的安装与配置2.1 下载 Chrome 浏览器的驱动程序2.2 配置环境变量三、Python 安装 Selenium四、页面元素定位4.1 选择浏览器开…
阅读更多...
基于JAVA的数据可视化的智慧河南大屏 开源项目

基于JAVA的数据可视化的智慧河南大屏 开源项目

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示四、核心代码4.1 数据模块 A4.2 数据模块 B4.3 数据模块 C4.4 数据模块 D4.5 数据模块 E 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的数据可视化的智慧河南大屏&#xff0c;包含了GDP、…
阅读更多...
MT8766安卓核心板/开发板_MTK联发科4G安卓手机主板方案定制开发

MT8766安卓核心板/开发板_MTK联发科4G安卓手机主板方案定制开发

MT8766采用台积电 12 nm FinFET 制程工艺&#xff0c;4*A53架构&#xff0c;Android 9.0操作系统&#xff0c;搭载2.0GHz 的 Arm NEON 引擎。提供了支持最新 OpenOS 及其要求苛刻的应用程序所需的处理能力&#xff0c;专为具有全球蜂窝连接的高移动性和功能强大的平板设备而设计…
阅读更多...
如何实现IOS APP被杀掉后依然可以接收到个推消息通知

如何实现IOS APP被杀掉后依然可以接收到个推消息通知

背景 项目已经集成了个推SDK&#xff0c;但是在离线场景下无法收到推送消息&#xff0c;离线场景主要分2种情况&#xff0c;一种是用户将APP切换到了后台&#xff0c;一种是用户将APP杀掉了。 针对场景一&#xff1a;我们可以将APP支持后台运行&#xff0c;比如项目中使用到了…
阅读更多...
【STM32单片机】步进电机控制系统设计

【STM32单片机】步进电机控制系统设计

文章目录 一、主要功能二、软件设计三、实验现象联系作者 一、主要功能 本项目使用STM32F103C8T6单片机控制器&#xff0c;使用ULN2003电机模块、IIC OLED模块、按键模块等。 主要功能&#xff1a; 系统运行后&#xff0c;OLED显示电机当前运行档位、方向、状态。 可通过按键…
阅读更多...
【Python从入门到进阶】46、58同城Scrapy项目案例介绍

【Python从入门到进阶】46、58同城Scrapy项目案例介绍

接上篇《45、Scrapy框架核心组件介绍》 上一篇我们学习了Scrapy框架的核心组件的使用。本篇我们进入实战第一篇&#xff0c;以58同城的Scrapy项目案例&#xff0c;结合实际再次巩固一下项目结构以及代码逻辑的用法。 一、案例网站介绍 58同城是一个生活服务类平台&#xff0c…
阅读更多...
13个自媒体文库平台（附通道链接）

13个自媒体文库平台（附通道链接）

划到最后“阅读原文” ——进入官网 Hi&#xff0c;我是胡猛夫&#xff0c;每天分享实用运营工具&#xff01; 更多内容&#xff0c;更多资源&#xff0c;欢迎交流&#xff01; 公 号 | 微视角文化 》》精彩推荐 >>微视角文化知识库&#xff1a;移动的自媒体运营百科全…
阅读更多...
rpb/rpc文件说明与matlab读取

rpb/rpc文件说明与matlab读取

什么是rpb/rpc文件&#xff1f; rpb文件是用来存储用于遥感数据几何校正的RPC&#xff08;Rational Polynomial Coefficients &#xff09;模型的文件。类似的还有RPC文件&#xff0c;rpb与rpc文件只是格式不同&#xff0c;但包含的信息一致。其用于从图像坐标转换到地理坐标&a…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023