启幕数据结构算法雅航新章，穿梭C++梦幻领域的探索之旅——二叉树序列构造探秘——堆的奥义与实现诗篇

devtools/2025/3/19 9:33:42/

在这里插入图片描述

在这里插入图片描述

人无完人，持之以恒，方能见真我！！！
共同进步！！

文章目录

  • 一、堆的定义与结构
  • 二、堆的实现
    • 1.堆的初始化和销毁
      • 堆的初始化
      • 堆的销毁
    • 2.向上调整算法和入堆
    • 3.向下调整算法和出堆顶数据
    • 4.堆的有效数据个数和判空
      • 堆的有效数据个数
      • 堆的判空
    • 5.取堆顶数据
  • 三、堆的源码

一、堆的定义与结构

堆的本质是一颗完全二叉树，只是它的要求比完全二叉树更加严格，它要求每颗子树的根节点都是当前子树的最大值或最小值，当根节点是最大值时，它就是一个大根堆，当根节点是最小值时，它就是一个小根堆

在上篇文章中我们也提到了，存储完全二叉树可以使用数组，存储非完全二叉树可以使用链表，而堆就是一种特殊的完全二叉树，所以堆的存储我们就使用数组，也就是顺序表的形式，如图：

在这里插入图片描述

我们将堆这个完全二叉树从上至下，从左至右的数据存放在数组中，至于怎么保证它每颗子树的根节点都是当前子树的最大值或最小值，我们在入堆和出堆的位置细讲，而顺序表的结构我们已经很熟悉了，这里直接写出来：

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

二、堆的实现

1.堆的初始化和销毁

堆的初始化

堆的初始化就是将数组置空，有效数据个数和容量大小置0，如下：

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

堆的销毁

堆的销毁就是先判断数组是否为空，不为空就将它释放掉，因为数组的空间是我们向操作系统申请来的，不会主动释放，如果我们不主动释放就会造成内存泄漏，最后我们将数组置空，有效数据个数和容量大小置0，如下：

//销毁
void HPDestroy(HP* php)
{assert(php);if (php->arr)//不为空就释放{free(php->arr);}php->arr = NULL;php->size = php->capacity = 0;
}

2.向上调整算法和入堆

接下来就是入堆操作，也就是向堆中插入数据，但是我们要知道，一般往数组中插入数据都是向数组尾部插入，那么是不是就会出现，原本堆的每颗子树的根节点都是当前子树的最大值或最小值，但是从尾部插入数据后会打破这个平衡，如图：

在这里插入图片描述
在这里插入图片描述

可以看到，原本的堆是一个小根堆，但是我们插入一个5之后，它就不构成小根堆了，这个时候就要用到我们的向上调整算法，当然，如果插入一个数据后还依然构成小根堆的话，我们就不做处理即可

向上调整算法

在讲解向上调整算法时，我们就统一以小根堆为例，向上调整算法的本质就是将我们插入的数据当作孩子节点，让它和它的父节点进行比较

那么有了孩子节点，怎么找到父节点呢？其实我们在上一篇讲过，父节点parent的下标等于(child-1)/2，找到父节点后，我们就看插入的数据是不是比它的父节点还小，如果是那么就直接进行交换，否则就不做操作，如图：

在这里插入图片描述

在这里插入图片描述

但是我们发现交换一次后还是没有构成小根堆，所以向上调整算法要求，只要我们做了交换，那么就让child走到parent，parent再走到新的child的父节点，继续进行比较，直到child为0，此时它就没有父亲节点了，停止向上调整，如图：

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}//向上调整
void AdjustUp(HPDataType* arr,int child)
{//根据传来的孩子节点算父亲节点int parent = (child - 1) / 2;//child>0是循环条件,因为要保证数据是数组元素while (child > 0){//如果是建小堆，就是<if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);//更新父节点和子节点child = parent;parent = (child - 1) / 2;}else//child >= parent，不用交换{break;}}
}

这里是建小根堆的写法，如果想要建大堆，那么将 小于 改成 大于 即可

入堆

有了向上调整算法我们入堆就很简单了，只需要将数据插入到数组最后，然后调用向上调整函数，就可以让我们的堆不被打乱

但是我们同时要注意，插入数据之前要检查数组空间大小是否足够，如果不够的话要进行扩容，如下：

//入堆
void HPPush(HP* php, HPDataType x)
{assert(php);//入堆前检查空间，不够就扩容if (php->size == php->capacity){//判断capacity是否相等于0，不相等就给2倍php->capacity = php->capacity == 0 ? 4 : 2 * php->capacity;//使用realloc初始化tmp数组为0HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType) *(php->capacity));if (NULL == tmp){perror("realloc fail\n");return;}php->arr = tmp;php->capacity *= 2;//这一步不要忘记}//判断空间后，存放数据php->arr[php->size] = x;//向上调整AdjustUp(php->arr, php->size);php->size++;
}

3.向下调整算法和出堆顶数据

在正式了解向下调整算法和出堆顶数据之前，首先我们要知道堆删除数据是删除堆顶的数据，也就是下标为0的数据，因为堆顶的数据是最特殊的，它是整个堆最大或最小的值，我们在堆的应用会讲到它的用法

那么了解了这一点之后，我们再来想想怎么删除堆顶数据，如果直接头删的话，那么之前堆的结构会完全乱套，我们画个图就知道了，以小根堆为例，如下：

在这里插入图片描述

在这里插入图片描述

可以看到如果我们直接对堆进行头删的话，整个堆的数据都被打乱了，结构也变乱了，我们要调整的话也无从下手，接下来我们就来介绍删除堆顶数据的正确做法

删除堆顶数据的正确做法就是，交换最后一个数据和堆顶数据，然后让size- -，这样我们就只会影响最后一个数据和堆顶数据，不会影响其它节点，如图：

在这里插入图片描述
在这里插入图片描述

经过上面的操作，我们就可以发现，我们删除了堆顶数据，只是说将堆中的最后一个数据移到了堆顶，但是也只改变了堆中的最后一个数据的位置，不至于像头删那样将整个堆的结构打乱

那么将堆中的最后一个数据放到了堆顶，此时堆很可能不是一个有效的堆，所以我们需要从堆顶向下调整整个堆，我们需要一个向下调整算法

向下调整算法

经过上面的分析，我们知道堆删除数据后，堆顶元素可能不符合堆的要求，所以我们要从堆顶开始向下调整，要注意的是，我们举例都是以小根堆为例

具体方法就是，将堆顶当作父节点parent，根据2*parent找到它的孩子节点child，最后让父节点和孩子节点进行比较，如果孩子节点更小就进行交换，然后让父亲走到孩子的位置，孩子再走到新父亲的孩子节点

如果孩子节点比父节点更大的话就不做修改，跟我们的向上调整算法类似，但是我们要注意一个点，我们在向下调整的时候，需要看当前父节点的左孩子和右孩子谁小，父节点要和小的那个孩子进行交换，为什么呢？

因为如果父节点和较大的那个孩子进行交换的话，较大的那个孩子就成了堆顶，另一个较小的孩子就比堆顶小，不满足小根堆的条件，如图：

在这里插入图片描述

可以发现，在这种情况下，我们经过交换后并不符合堆的要求，因为原本的右孩子较小，但是父节点是和左孩子进行交换的，导致较大的左孩子到了堆顶，不符合堆的要求

所以我们在进行向下调整时，找到左孩子child后，还要先判断一下左右孩子谁更小，如果左孩子更小就不需要做更改，如果右孩子更小就让child++，这样就可以让child走到更小的右孩子了(注意左右孩子的关系，右孩子比左孩子的下标大1)

那么有了正确的思路之后我们重新走一遍上面的过程，看看有没有问题，如图：

在这里插入图片描述
在这里插入图片描述

通过一系列的画图分析，我们直接根据思路写出对应的代码即可，如下：

//向下调整--多传一个n，是循环的结束条件
void AdjustDown(HPDataType* arr, int parent, int n)
{//根据父节点算出左孩子int child = parent * 2 + 1;while (child < n)//向下调整不能越界{//如果右孩子存在,并且比左孩子小if (child + 1 < n && arr[child + 1] < arr[child]){child++;//就让孩子变成右孩子}//孩子小于父亲就交换if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);//交换后，更新child 、 parentparent = child;child = 2 * parent + 1;}else{//父节点小于子节点break;}}
}

出堆

上面我们其实已经完整讲解了出堆的过程，这里我们再次回顾一下，出堆就是指删除堆中的堆顶数据，方法就是交换堆顶和最后一个数据，让size- -，间接删除了堆顶数据，然后最后一个数据到了堆顶，再对它进行向下调整即可
   那么有了思路我们就可以直接写代码了，如下：

//出堆顶元素
void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));//堆不为空才出堆//删除数据---size是总大小，所以-1是最后一个元素的下标Swap(php->arr[0], &php->arr[php->size-1]);//交换首尾元素php->size--;//交换删除后，得到新首尾，向下调整AdjustDown(php->arr, 0, php->arr);//0是父节点
}

4.堆的有效数据个数和判空

堆的有效数据个数

堆的有效数据个数由size记录，直接返回size即可

//堆的有效数据个数
int HPSize(HP* php)
{assert(php);return php->size;
}

堆的判空

堆的判空就是判断堆的有效数据个数是否为0，也是跟size相关

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

5.取堆顶数据

取堆顶数据就是取堆中下标为0位置的数据

//取堆顶元素
HPDataType HPTop(HP* php)
{assert(php);return php->arr[0];
}

三、堆的源码

#include <stdio.h>
#include <errno.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int HPDataType;typedef struct Heap
{HPDataType* arr;int size;int capacity;
}HP;#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"//初始化
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;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}//向上调整
void AdjustUp(HPDataType* arr,int child)
{//根据传来的孩子节点算父亲节点int parent = (child - 1) / 2;//child>0是循环条件,因为要保证数据是数组元素while (child > 0){//如果是建小堆，就是<if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);//更新父节点和子节点child = parent;parent = (child - 1) / 2;}else//child >= parent，不用交换{break;}}
}//入堆
void HPPush(HP* php, HPDataType x)
{assert(php);//入堆前检查空间，不够就扩容if (php->size == php->capacity){//判断capacity是否相等于0，不相等就给2倍php->capacity = php->capacity == 0 ? 4 : 2 * php->capacity;//使用realloc初始化tmp数组为0HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType) *php->capacity);if (NULL == tmp){perror("realloc fail\n");return;}php->arr = tmp;php->capacity *= 2;//这一步不要忘记}//判断空间后，存放数据php->arr[php->size] = x;//向上调整AdjustUp(php->arr, php->size);php->size++;
}//向下调整--多传一个n，是循环的结束条件
void AdjustDown(HPDataType* arr, int parent, int n)
{//根据父节点算出左孩子int child = parent * 2 + 1;while (child < n)//向下调整不能越界{//如果右孩子存在,并且比左孩子小if (child + 1 < n && arr[child + 1] < arr[child]){child++;//就让孩子变成右孩子}//孩子小于父亲就交换if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);//交换后，更新child 、 parentparent = child;child = 2 * parent + 1;}else{//父节点小于子节点break;}}
}//判空
bool HPEmpty(HP* php)
{return php->size == 0;
}//出堆顶元素
void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));//堆不为空才出堆//删除数据---size是总大小，所以-1是最后一个元素的下标Swap(php->arr[0], &php->arr[php->size-1]);//交换首尾元素php->size--;//交换删除后，得到新首尾，向下调整AdjustDown(php->arr, 0, php->arr);//0是父节点
}//堆的有效数据个数
int HPSize(HP* php)
{assert(php);return php->size;
}//取堆顶元素
HPDataType HPTop(HP* php)
{assert(php);return php->arr[0];
}

http://www.ppmy.cn/devtools/168302.html

相关文章

深度学习之防止过拟合

深度学习之防止过拟合

过拟合是机器学习中常见的问题，特别是当模型复杂度较高或训练数据量较少时。为了避免模型过度依赖训练数据中的噪声，采取一些有效的防止过拟合的方法非常重要。以下是几种常见的防止过拟合的技术，包括 Dropout、数据增强、正则化 等，并对它们进行详细的介绍与对比。 1. Dr…
阅读更多...
IP 协议

IP 协议

文章目录 IP 协议概述数据包格式首部校验和实例分析实例一 分片抓包分析参考 本文为笔者学习以太网对网上资料归纳整理所做的笔记&#xff0c;文末均附有参考链接&#xff0c;如侵权&#xff0c;请联系删除。 IP 协议 概述 IP 协议是 TCP/IP 协议簇中的核心协议&#xff0c;也…
阅读更多...
MySQL--DDL

MySQL--DDL

1、DDL-数据库操作 查询&#xff1a; 查询所有数据库&#xff1a; SHOW DATABASES; 查询当前数据库&#xff1a; SELECT DATABASE(); 创建: CREATE DATABASE[IF NOT EXISTS] 数据库名 [DEFAULT CHARSET 字符集] [COLLATE 排序规则]&#xff1b; 删…
阅读更多...
JVM部分八股

JVM部分八股

什么是JVM&#xff1f; 有哪些好处&#xff1f; 索引越界可能导致程序覆盖其他程序内存中的代码 JVM是一套规范&#xff0c;有多种实现 JVM运行流程&#xff1f; 1.类加载器将java程序翻译为java字节码文件 2.运行数据区将字节码文件加载到内存&#xff0c;字节码文件是J…
阅读更多...
【计算机视觉】工业表计读数（2）--表计检测

【计算机视觉】工业表计读数（2）--表计检测

1. 简介 工业表计&#xff08;如压力表、电表、气表等&#xff09;在工控系统、能源管理等领域具有重要应用。然而&#xff0c;传统人工抄表不仅工作量大、效率低&#xff0c;而且容易产生数据误差。近年来&#xff0c;基于深度学习的目标检测方法在工业检测中展现出极大优势&…
阅读更多...
【第13节】windows sdk编程：GDI编程

【第13节】windows sdk编程：GDI编程

目录 一、GDI 概述 二、设备环境概念 三、使用 GDI 绘图对象 四、使用 GDI 坐标系统 五、使用GDI绘图 5.1 输出文字 5.2 画点和线 5.3 画矩形框、圆和多边形 5.4 画位图和图标 5.5 双缓冲技术 六、综合代码示例 一、GDI 概述 Windows 应用程序不支持标准输出函数&am…
阅读更多...
【最佳实践】Go 状态模式

【最佳实践】Go 状态模式

设计思路 状态模式的核心在于将对象的行为封装在特定的状态类中&#xff0c;使得对象在不同的状态下表现出不同的行为。每个状态实现同一个接口&#xff0c;允许对象在运行时通过改变其内部状态对象来改变其行为。状态模式使得状态转换更加明确&#xff0c;并且易于扩展新的状…
阅读更多...
蓝桥杯学习-01好数

蓝桥杯学习-01好数

01枚举 1.好数 问题描述 一个整数如果按从低位到高位的顺序&#xff0c;奇数位 (个位、百位、万位 ⋯⋯ ) 上的数字是奇数&#xff0c;偶数位 (十位、千位、十万位 ⋯⋯ ) 上的数字是偶数&#xff0c;我们就称之为 “好数”。 给定一个正整数 NN&#xff0c;请计算从 1 到 …
阅读更多...
最新文章

Copyright @ 2022~2023