DS：堆的结构与实现

2024-06-10 00:28
文章标签 实现 结构 ds

本文主要是介绍DS：堆的结构与实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎来到Harper.Lee的学习世界！
博主主页传送门：Harper.Lee的博客主页
想要一起进步的uu可以来后台找我哦！

一、堆的概念与结构

1.1 堆的概念

堆（Heap）是完全二叉树中的一种，分为大根堆和小根堆。
特点：1.每个节点的值都大于或等于其左右孩子节点的值，称为大根堆；或是每个节点的值都小于或等于其左右孩子的值，称为小根堆。2.从堆的概念不难看出，大根堆堆顶为集合的最大值，小根堆堆顶为集合的最小值。（注意：父亲与孩子之间有大小关系，但是兄弟之间没有大小关系，因此堆并不是有序的！！！）

1.2 堆的结构

根据上一节（DS：树与二叉树的相关概念）可知，完全二叉树以数组的形式存储，因此堆采用数组的形式进行数据的存储。
父子的下标特点：(1)父亲找孩子：leftchild=parent2+1，rightchild=parent2+2；(2)孩子找父亲：parent=（child-1）/2。
image.png

二、堆的实现

2.0 分析过程

插入数据部分分析过程：
image.png

2.1 堆的相关结构体的创建

堆的底层是数组，因此结构体就以数组的形式创建。这一步和之前顺序表的创建基本一样。

//结构体的创建
typedef int HPDataType;
typedef struct Heap
{//以数组为背景HPDataType* a;int size;//表示存储的数据个数int capacity;//表示空间容量，因为我么虽然操作的是二叉树
}HP;

2.2 堆的初始化

//初始化
void HPInit(HP* php)
{//Q：这里需要断言吗？？?  A：php需要断言,避免传入空堆assert(php);php->a = NULL;php->capacity = php->size = 0;//可以给值，也可以不给值（前面有讲过）//如果capacity和size不给值的话，在插入数据的时候就需要动态申请开辟空间//如果capacity和size赋值的话，就是另外的一种操作。
}

2.3 堆的插入

push就有建立堆的功能。一边插入数据，一边调整出堆的结构。

//push堆的操作
void HPPush(HP* php,HPDataType x)//传入堆，插入一个数据x
{assert(php);//1. 先判断空间是否足够//1. 若空间不够（说明之前有空间的，即使没有空间，capacity也等于size），则进行增容操作if (php->capacity == php->size)//if (php->capacity == php->size == 0)，而不是判断是否为空{int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("malloc fail");exit(1);//return;//直接返回也可}php->a = tmp;php->capacity = newcapacity;}//2. 开始插入数据php->a[php->size] = x;//php->size++;//3. 调用向上调整函数AdjustUp(php->a, php->size-1);//为什么第2个参数是size-1而不是size?----要弄清楚size的位置：最后一个数据位置的下标+1
}

2.4 向上调整算法

//向上调整函数的定义
void AdjustUp(HPDataType* a, int child)//从child的位置开始调整，现在child就是数组末尾了
{//虽然控制的十足，但是要把它想象成实在控制二叉树（堆）//1.第一次插入的数据在数组的末尾child位置int parent = (child - 1) / 2;//父节点的位置找到了//2.开始比较父节点和子节点--小根堆：谁小谁当爹//循环三要素：a.初始条件b.中间过程c.结束条件/*while (a[parent] >= 0)//为什么循环结构是>=0?因为实际上最初始的child从末尾开始就需要和她的所有祖先（一条线上的）全部进行比较，比较完循环才会结束）*///如果用parent>=0来判断，那么由于（0-1）/2是-1/2，取整后还是0，就会再次进入循环，一般情况来说这是错误的，但是这里出现了一个巧合：parent==child==0，break跳出循环了，程序歪打正着的正确了。while (a[child] > 0)//上面的循环条件写成下面这种会更好{  if (a[child] < a[parent]){//3.开始进行交换操作（Swap函数的调用）Swap(&a[child], &a[parent]);child = parent;//调整身份继续向上进行下一次（循环可能出现）可能出现的比较parent = (child - 1) / 2;//原来的父亲变成孩子（父亲赋值给孩子），然后原来的父亲变成了前一个祖先。}else{break;// 满足小根堆的结构}}
}

2.5 交换函数

//Swap函数的调用
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp;tmp = *a;*a = *b;*b = tmp;
}

2.6 堆的删除

删除堆的末尾数据是没意义的，因为这个操作很简单，封装成函数就是小题大做了。因此，我们一般删除的是堆顶数据即根位置的数据。但是，如果直接删除/挪动/覆盖了堆顶数据，可能父子关系、叔侄关系、兄弟关系会乱套，倒反天罡了。
所以我么选择一种新的解决办法：根节点的数据和尾节点的数据进行交换，然后再删除尾节点的数据，然后进行向下调整算法重新调整堆的结构，这样就实现了堆顶元素的删除。

分析过程如下：image.png
代码实现：

//Pop删除数据——要求删除堆顶即根位置的数据，删除末尾数据没有意义
void HPPop(HP* php)
{assert(php);//1.将堆顶元素和最后一个元素进行交换Swap(&php->a[php->size-1], &php->a[0]);//尾元素：a[size-1]//2.删除堆中的最后一个元素的数据---怎么删啊?---删除数组中最后一个元素的数据//free(php->a[php->size-1]);//不能使用free，因为内存申请的空间必须一块儿释放，而不是一部分一部分地释放的php->size--;//php->size -= 1;//3.向下调整算法的运用AdjustDown(php->a, php->size, 0);
}

Q1：删除堆顶数据有什么意义或者作用呢？

删除掉了目前堆里最小的元素，相当于取出来堆中的最小的元素。如果连续使用HPPop函数，那么就可以从小到大依次取出堆中的数据，这就是简单模式的TOP-K。

Q2：HPPop的时间复杂度是多少？

pop的时间复杂度为logN（最坏情况），O(1)（最好情况）。而满二叉树/完全二叉树的树高就是logN。

应用：可以一边HPTop获取堆中目前的最小的数据，然后HPPop删除掉这个数据，这样就可以进行排序打印了。

2.7 向下调整算法

//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)//从parent根节点开始调整
{//1.先确定（假设法）用哪个孩子与父亲做比较//假设左孩子比右孩子小int child = parent * 2 + 1;//根据父节点找到子节点while (child < n)//child>=n时，说明该孩子已经不存在了 {//找出小的孩子//if (a[child + 1] < a[child])//此写法存在风险：左孩子<n没有风险，但是右孩子+1就可能存在风险if (child + 1 < n && a[child + 1] < a[child]){//如果右孩子比左孩子小：假设不成立，修改假设的内容：++child;//child右移变成右孩子}//2.小孩子与父亲做比较if (a[child] < a[parent]){Swap(&a[parent], &a[child]);//3.交换后进行父亲与孩子的调整parent = child;child = parent * 2 + 1;}else{break;}}
}

2.8 获取堆顶的数据

//获取堆顶的数据（返回堆顶元素）
HPDataType HPTop(HP* php)//top-k问题
{//断言：assert(php);assert(php->size > 0);return php->a[0];
}

2.9 判空

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

2.10 堆的销毁

//销毁
void HPDestroy(HP* php)
{assert(php);free(php->a);php->capacity = php->size = 0;php->a == NULL;
}

2.11 前k个元素的打印

main函数中堆的建立过程以及打印实现过程：

//
int main()
{int a[] = { 4,2,8,1,5,6,9,7 };//这个数组现在还不是堆，需要将其变成一个堆（一个个地去插入）HP hp;//1.创建一个堆hp//2.初始化HPInit(&hp);//3.建堆（需要插入多个数据，因此，需要多次调用HPPush函数，使用循环结构）for (int i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);//建堆的同时 调整了堆的结构}//4.打印堆中的所有数据//while (!HPEmpty(&hp))//{//	printf("%d ", HPTop(&hp));//获取到堆顶的数据//	HPPop(&hp);//}//5.如果是找堆里的最大的前k个数据int k = 0;scanf("%d", &k);while (k--){printf("%d ", HPTop(&hp));HPPop(&hp);}printf("\n");HPDestroy(&hp); return 0;
}

这里是实现了打印上的有序，但是数组本身并不有序。我们可以将每次HPTop操作获得的堆顶数据放在a数组中，就可以使得数组有序了。也就是上一段代码中注释掉的第 4. 点

	//4.打印堆中的所有数据//while (!HPEmpty(&hp))//{//	printf("%d ", HPTop(&hp));//获取到堆顶的数据//	HPPop(&hp);//}//6. 数组a有序的改变int i = 0;while (!HPEmpty(&hp)){//printf("%d ", HPTop(&hp));//获取到堆顶的数据a[i++] = HPTop(&hp);HPPop(&hp);}

三、堆的实现-全部代码

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//本次-----堆的实现过程 —— 框架//1. 结构体的创建
typedef int HPDataType;
typedef struct Heap
{//以数组为背景HPDataType* a;int size;//表示存储的数据个数int capacity;//表示空间容量，因为我么虽然操作的是二叉树
}HP;//2. 初始化和销毁
void HPInit(HP* php);//php是结构体指针变量
void HPDestroy(HP* php);
//3. 插入HPDataType类型数据x（节点），注意保持堆的完整结构
void HPPush(HP* php, HPDataType x);
//4. Pop删除数据——要求删除堆顶即根位置的数据
void HPPop(HP* php); 
//5. 向下调整法
void AdjustUp(HPDataType* a,int child);
//6. 向上调整法
void AdjustDown(HPDataType* a, int n, int parent);
//7. 判断堆结构是否为空
bool HPEmpty(HP* php);
//8. 交换函数
void Swap(HPDataType* a, HPDataType* b);
//9. 获取堆顶数据
HPDataType HPTop(HP* php);
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"//（1） 初始化
void HPInit(HP* php)//传入堆（php是堆的名称）
{//Q：这里需要断言吗？？?  A：php需要断言,避免传入空堆assert(php);php->a = NULL;php->capacity = php->size = 0;//可以给值，也可以不给值（前面有讲过）//如果capacity和size不给值的话，在插入数据的时候就需要动态申请开辟空间//如果capacity和size赋值的话，就…………？？？两种玩法一样
}//（2） 销毁（free释放掉动态申请的空间）
void HPDestroy(HP* php)
{assert(php);free(php);//释放掉空间后记得善后php->capacity = php->size = 0;php->a = NULL;
}//（5）Swap函数的调用
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp;tmp = *a;*a = *b;*b = tmp;
}//（4） 向上调整函数的定义
void AdjustUp(HPDataType* a, int child)//从child的位置开始调整，现在child就是数组末尾了
{//虽然控制的十足，但是要把它想象成实在控制二叉树（堆）//1.第一次插入的数据在数组的末尾child位置int parent = (child - 1) / 2;//父节点的位置找到了//2.开始比较父节点和子节点--小根堆：谁小谁当爹//循环三要素：a.初始条件b.中间过程c.结束条件/*while (a[parent] >= 0)//为什么循环结构是>=0?因为实际上最初始的child从末尾开始就需要和她的所有祖先（一条线上的）全部进行比较，比较完循环才会结束）*///如果用parent>=0来判断，那么由于（0-1）/2是-1/2，取整后还是0，就会再次进入循环，一般情况来说这是错误的，但是这里出现了一个巧合：parent==child==0，break跳出循环了，程序歪打正着的正确了。while (a[child] > 0)//上面的循环条件写成下面这种会更好{  if (a[child] < a[parent]){//3.开始进行交换操作（Swap函数的调用）Swap(&a[child], &a[parent]);child = parent;//调整身份继续向上进行下一次（循环可能出现）可能出现的比较parent = (child - 1) / 2;//原来的父亲变成孩子（父亲赋值给孩子），然后原来的父亲变成了前一个祖先。}else{break;// 满足小根堆的结构}}
}//（3） push堆的操作
void HPPush(HP* php,HPDataType x)//传入堆，插入一个数据x
{assert(php);//1. 先判断空间是否足够//1. 若空间不够（说明之前有空间的，即使没有空间，capacity也等于size），则进行增容操作if (php->capacity == php->size)//if (php->capacity == php->size == 0)，而不是判断是否为空{int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("malloc fail");exit(1);//return;//直接返回也可}php->a = tmp;php->capacity = newcapacity;}//2. 开始插入数据php->a[php->size] = x;//php->size++;//3. 调用向上调整函数AdjustUp(php->a, php->size-1);//为什么第2个参数是size-1而不是size?----要弄清楚size的位置：最后一个数据位置的下标+1
}//（7）向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)//从parent根节点开始调整
{//1.先确定（假设法）用哪个孩子与父亲做比较//假设左孩子比右孩子小int child = parent * 2 + 1;//根据父节点找到子节点while (child < n)//child>=n时，说明该孩子已经不存在了 {//找出小的孩子//if (a[child + 1] < a[child])//此写法存在风险：左孩子<n没有风险，但是右孩子+1就可能存在风险if (child + 1 < n && a[child + 1] < a[child]){//如果右孩子比左孩子小：假设不成立，修改假设的内容：++child;//child右移变成右孩子}//2.小孩子与父亲做比较if (a[child] < a[parent]){Swap(&a[parent], &a[child]);//3.交换后进行父亲与孩子的调整parent = child;child = parent * 2 + 1;}else{break;}}
}//（6）Pop删除数据——要求删除堆顶即根位置的数据，删除末尾数据没有意义
void HPPop(HP* php)//logN
{assert(php);assert(php->size > 0);//1.将堆顶元素和最后一个元素进行交换Swap(&php->a[php->size-1], &php->a[0]);//尾元素：a[size-1]//2.删除堆中的最后一个元素的数据---怎么删啊?---删除数组中最后一个元素的数据//free(php->a[php->size-1]);//不能使用free，因为内存申请的空间必须一块儿释放，而不是一部分一部分地释放的php->size--;//php->size -= 1;//3.向下调整算法的运用AdjustDown(php->a, php->size, 0);
}//（7）获取堆顶的数据（返回堆顶元素）
HPDataType HPTop(HP* php)//top-k问题
{//断言：assert(php);assert(php->size > 0);//作用？？return php->a[0];
}
//（8）判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"int main()
{ int a[] = { 4,2,8,1,5,6,9,7 };//这个数组现在还不是堆，需要将其变成一个堆（一个个地去插入）HP hp;//1.创建一个堆hp//2.初始化HPInit(&hp);//3.建堆（需要插入多个数据，因此，需要多次调用HPPush函数）for (int i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);//建堆的同时 调整了堆的结构}//1. 打印堆中的所有数据//while (!HPEmpty(&hp))//{//	printf("%d ", HPTop(&hp));//获取到堆顶的数据//	HPPop(&hp);//}//如果是找堆里的最大的前k个数据int k = 0;scanf("%d", &k);while (k--){printf("%d ", HPTop(&hp));HPPop(&hp);}printf("\n");return 0;
}

喜欢的uu记得三连支持哦！
在这里插入图片描述

这篇关于DS：堆的结构与实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1046727。

相关文章

MySQL中On duplicate key update的实现示例

MySQL中On duplicate key update的实现示例

《MySQL中Onduplicatekeyupdate的实现示例》ONDUPLICATEKEYUPDATE是一种MySQL的语法,它在插入新数据时,如果遇到唯一键冲突,则会执行更新操作,而不是抛... 目录1/ ON DUPLICATE KEY UPDATE的简介2/ ON DUPLICATE KEY UP
阅读更多...
Python中Json和其他类型相互转换的实现示例

Python中Json和其他类型相互转换的实现示例

《Python中Json和其他类型相互转换的实现示例》本文介绍了在Python中使用json模块实现json数据与dict、object之间的高效转换,包括loads(),load(),dumps()... 项目中经常会用到json格式转为object对象、dict字典格式等。在此做个记录，方便后续用到该方
阅读更多...
JWT + 拦截器实现无状态登录系统

JWT + 拦截器实现无状态登录系统

《JWT+拦截器实现无状态登录系统》JWT（JSONWebToken）提供了一种无状态的解决方案：用户登录后,服务器返回一个Token,后续请求携带该Token即可完成身份验证,无需服务器存储会话... 目录✅ 引言 一、JWT 是什么？ 二、技术选型 三、项目结构 四、核心代码实现4.1 添加依赖（pom
阅读更多...
SpringBoot路径映射配置的实现步骤

SpringBoot路径映射配置的实现步骤

《SpringBoot路径映射配置的实现步骤》本文介绍了如何在SpringBoot项目中配置路径映射,使得除static目录外的资源可被访问,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一... 目录SpringBoot路径映射补：springboot 配置虚拟路径映射 @RequestMapp
阅读更多...
Python与MySQL实现数据库实时同步的详细步骤

Python与MySQL实现数据库实时同步的详细步骤

《Python与MySQL实现数据库实时同步的详细步骤》在日常开发中,数据同步是一项常见的需求,本篇文章将使用Python和MySQL来实现数据库实时同步,我们将围绕数据变更捕获、数据处理和数据写入这... 目录前言摘要概述：数据同步方案1. 基本思路2. mysql Binlog 简介实现步骤与代码示例1
阅读更多...
Redis实现高效内存管理的示例代码

Redis实现高效内存管理的示例代码

《Redis实现高效内存管理的示例代码》Redis内存管理是其核心功能之一,为了高效地利用内存,Redis采用了多种技术和策略,如优化的数据结构、内存分配策略、内存回收、数据压缩等,下面就来详细的介绍... 目录1. 内存分配策略jemalloc 的使用2. 数据压缩和编码ziplist示例代码3. 优化的
阅读更多...
基于C#实现PDF转图片的详细教程

基于C#实现PDF转图片的详细教程

《基于C#实现PDF转图片的详细教程》在数字化办公场景中,PDF文件的可视化处理需求日益增长,本文将围绕Spire.PDFfor.NET这一工具,详解如何通过C#将PDF转换为JPG、PNG等主流图片... 目录引言一、组件部署二、快速入门：PDF 转图片的核心 C# 代码三、分辨率设置 - 清晰度的决定因
阅读更多...
Java Kafka消费者实现过程

Java Kafka消费者实现过程

《JavaKafka消费者实现过程》Kafka消费者通过KafkaConsumer类实现,核心机制包括偏移量管理、消费者组协调、批量拉取消息及多线程处理,手动提交offset确保数据可靠性,自动提交... 目录基础KafkaConsumer类分析关键代码与核心算法2.1 订阅与分区分配2.2 拉取消息2.3
阅读更多...
SpringBoot集成XXL-JOB实现任务管理全流程

SpringBoot集成XXL-JOB实现任务管理全流程

《SpringBoot集成XXL-JOB实现任务管理全流程》XXL-JOB是一款轻量级分布式任务调度平台,功能丰富、界面简洁、易于扩展,本文介绍如何通过SpringBoot项目,使用RestTempl... 目录一、前言二、项目结构简述三、Maven 依赖四、Controller 代码详解五、Service
阅读更多...
Python 基于http.server模块实现简单http服务的代码举例

Python 基于http.server模块实现简单http服务的代码举例

《Python基于http.server模块实现简单http服务的代码举例》Pythonhttp.server模块通过继承BaseHTTPRequestHandler处理HTTP请求,使用Threa... 目录测试环境代码实现相关介绍模块简介类及相关函数简介参考链接测试环境win11专业版python
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2