堆的实现(偷懒版)

ops/2024/9/23 21:06:54/

                           🌹个人主页🌹:喜欢草莓熊的bear

                           🌹专栏🌹:数据结构


目录

前言

一、堆的实现

1.1 堆的向下调整算法

思路:

1.2 堆的向上调整算法

1.3 堆的创建

1.4 堆的复杂度计算

向下调整建堆的复杂度:

  向上调整建堆的复杂度:

1.5 堆的插入

1.6 堆的删除

1.7 堆的代码实现

总结


前言

在上期内容介绍了二叉树、还简单提了一下堆的概念和大堆、小堆。回顾一下堆是首先是完全二叉树,因为是完全二叉树所以使用数组储存比较合理。

一、堆的实现

1.1 堆的向下调整算法

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
给上一个例子
int arr[] = {27,15,19,18,28,34,65,49,25,37};

 上面这幅图就是向下调整的算法的过程图

思路:

 假设我们通过向下调整算法建立小堆,我们就需要从根的左右子树开始,比较得出左右子树小的那一个和根比较,谁小谁就是根。我们之前还介绍父亲节点和孩子节点的概念,我们这里就要使用到。根据我们上面的思路,向下调整算法需要通过比较还在节点后进行调整。所以我们需要知道父亲节点然后再找到孩子节点为什么要知道父亲节点呢?我们通过数组储存着堆,下标就可以帮助我们找到孩子节点。

 大致思路就是这样我们来写代码:

void Swap(HPDataType* x, HPDataType* y)//交换数据
{HPDataType tmp = *x;*x = *y;*y = tmp;
}void ADjustDown(HPDataType* a, int n,int parent)//向下调整
{int child = parent * 2 + 1;while (child < n){//假设法if (a[child] > a[child + 1] && child + 1 < n)//比较左右子树,找到较小的子树。{child++;}if (a[parent] > a[child])//数据交换{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

 解释一下个别代码,child + 1  < n 防止数组越界。 

1.2 堆的向上调整算法

 向上调整我们需要从最后一层向上调整,所以我们是通过孩子节点得到父亲节点。大致思路和向下调整一样,比较孩子节点的大小后再和父亲节点比较一直比较到根节点。根据child = parent *2+1 反推得到 parent = ( child -1 )/2 。

直接上代码:

void Swap(HPDataType* x, HPDataType* y)//交换数据
{HPDataType tmp = *x;*x = *y;*y = tmp;
}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.3 堆的创建

下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。
给上一个例子:
int a[] = {1,5,3,8,7,6};

1.4 堆的复杂度计算

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值,多几个节点不影响最终结果)

向下调整建堆的复杂度:

  向上调整建堆的复杂度:

是O(N) = N * logN 得到方法和向下调整一样推导就可以了。

1.5 堆的插入

先插入一个 10 到数组的尾上,再进行向上调整算法,直到满足堆。

 堆的插入需要用的向上调整

1.6 堆的删除

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。

 

1.7 堆的代码实现

堆的初始化、销毁都是很简单和之前写的栈啊等等都十分相似。剩下一些 获取堆顶元素、堆的个数、堆的判断都比较简单就不讲解了给上了代码。

typedef int HPDataType;typedef struct Heap//因为堆的定义就是满二叉树与完全二叉树,用数组储存非常好。
{HPDataType* a;//数组int size;int capacity;
}Heap;//小堆情况下的初始化
void HPInit(Heap* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}//销毁
void HPDestory(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}void Swap(HPDataType* x, HPDataType* y)//交换数据
{HPDataType tmp = *x;*x = *y;*y = tmp;
}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 ADjustDown(HPDataType* a, int n,int parent)//向下调整
{int child = parent * 2 + 1;while (child < n){//假设法if (a[child] > a[child + 1] && child + 1 < n){child++;}if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//入堆
void HPPush(Heap* php, HPDataType x)
{assert(php);//扩容if (php->size == php->capacity){int Newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, Newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("ralloc fail");return;}php->a = tmp;php->capacity = Newcapacity;}php->a[php->size++] = x; ADjustUp(php->a,php->size - 1);
}//出堆(消除堆顶数据)
void HPPop(Heap* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;ADjustDown(php->a,php->size,0);
}//取堆顶数据
HPDataType HPTop(Heap* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//堆的数据个数
int HPSize(Heap* php)
{assert(php);return php->size;
}//堆的判空
bool HPEmpty(Heap* php)
{assert(php);return php->size == 0;
}

总结

本节重点堆的向上、向下调整算法的代码实现 和 复杂度计算。


http://www.ppmy.cn/ops/93335.html

相关文章

AI换脸模型(384-448模型430万底丹)

模型训练素材19万张来自于 1、香港中文大学CelebA预训练集-WF512版-量大角度全-11万5千张 2、DST全角度训练图集V3.1 WF512【2.6W张 6GB 】 3、女性人脸数据&#xff0c;预训练炼丹专用 4、补全SRC极限角度 5、全角度512分辨率7万张素材 下载地址&#xff1a; 链接&#xf…

Tomcat 最大连接数实现原理

spring boot 内置tomcat设置连接数 max-connections: 5 server:port: 9898servlet:context-path: /testtomcat:connection-timeout: 5000max-connections: 5accept-count: 5 ##初始化连接数量connectionLimitLatch protected LimitLatch initializeConnectionLatch() {if (ma…

centos安装rclone挂载alist

一、安装alist 1.通过docker启动alist docker run -d --restartalways \-v /usr/local/docker/alist/data:/opt/alist/data \-p 5244:5244 \-e PUID$(id -u) \-e PGID$(id -g) \-e UMASK022 \--name alist \xhofe/alist:latest2.访问alist 使用docker logs alist在容器日志中…

docker部署rabbitMQ

docker部署rabbitMQ 如果用目录挂载会启动失败&#xff0c;要用数据卷挂载。 docker pull rabbitmq:3.8-management #挂载数据卷 -v mq-plugins:/plugins \ #设置主机名 --hostname mq \ docker run \-e RABBITMQ_DEFAULT_USERrabbitmq \-e RABBITMQ_DEFAULT_PASS1234 \-v mq…

Json-JacksonUtils工具类扩展(jackson转换Page)

如果你想使用 Jackson 来处理分页数据,通常会涉及到将分页结果转换成 JSON 或者从 JSON 反 序列化成分页结果。这里我们假设你正在使用一个类似于 Page 的分页模型,它可以包含分页数据 和一些元数据,如当前页数、总页数、总记录数等。 Page 类定义 首先定义一个 Page 类…

DuDuTalk:ASR与NLP技术,如何共同赋能AI智能工牌?

在人工智能瞬息万变的时代&#xff0c;AI智能工牌凭借其卓越的功能和广泛的应用场景正在逐步走入我们的日常生活。在这背后&#xff0c;自动语音识别&#xff08;ASR&#xff09;和自然语言处理&#xff08;NLP&#xff09;这两项关键技术&#xff0c;正是推动其快速发展的核心…

jenkins一键推送到远程服务器并用docker容器启动

1.安装jenkins 我后端使用的是宝塔面板来安装的容器化jenkins,要选中允许外部访问&#xff0c;安装完之后没有那个选项了&#xff0c;一开始安装的时候要选中不使用域名和后面的允许外部访问。Jenkins 版本为&#xff1a; 2.462.1 2.配置Jenkins 2.1 Git plugin 安装完毕之…

mysql 5.XX 设置中文数据报错

mysql 5.XX 默认是 拉丁文&#xff0c;需要手动修改为 utf8&#xff0c; 查看 库 表 ddl show create database mydatabase; show create table mytable; 可以看到 字符集信息 方法&#xff1a;修改mysql文件 my.ini