【数据结构】【C语言】堆~动画超详细解读！

目录

    • 1 什么是堆
      • 1.1 堆的逻辑结构和物理结构
      • 1.2 堆的访问
      • 1.3 堆为什么物理结构上要用数组?
      • 1.4 堆数据上的特点
    • 2 堆的实现
      • 2.1 堆类型定义
      • 2.2 需要实现的接口
      • 2.3 初始化堆
      • 2.4 销毁堆
      • 2.5 堆判空
      • 2.6 交换函数
      • 2.7 向上调整(小堆)
      • 2.8 向下调整(小堆)
      • 2.9 堆插入
      • 2.10 堆删除
      • 2.11 //堆顶
    • 3 完整代码
      • 3.1 heap.h
      • 3.2 heap.c

1 什么是堆

  • 简单来说堆是二叉树的一种表示方式,它在逻辑上就是一颗完全二叉树,它在物理上却是一个数组,这么说可能有点抽象,我们原来学习的栈,队列,或者说顺序表,链表等等,他们的逻辑结构和物理结构是相同或者相似的,就会比较好理解一些,而在堆这里物理结构和逻辑结构截然不同,理解相对就会比较抽象一些,我们接着看

1.1 堆的逻辑结构和物理结构

  • 逻辑结构即我们想象的结构,就比方说我们早上在图书馆排队的时候,放个包在图书馆门口,人可能都不见了,这个时候我们逻辑上认为我们在排队,但物理上我们同学就可能在吃早饭上厕所啥的
  • 逻辑上我们想象这个数组是一个二叉树,并且像二叉树一样访问子节点或者父节点
  • 比方说我给出以下数组,它在逻辑上是这样表示的(当然哈,指针其实是不存在的,只是逻辑上我们看作其是父子关系):
    请添加图片描述

1.2 堆的访问

  • 既然堆是一颗货真价实的二叉树,可我们怎么像二叉树一样,通过父/子节点访问子/父节点呢?

在这里插入图片描述

  1. 通过父节点访问子节点：
    • 我们假设父节点的下标为3,我们想访问它的子节点,只需要把 父节点的下标 * 2 + 1 或 父节点的下标 * 2 + 2 即可 即 7 或 8
  2. 通过子节点访问父节点
    • 我们假设子节点的下标为7,我们想访问它的父节点,只需要把 (子节点的下标 - 1) / 2 即可 即 3
    • 我们假设子节点的下表为8,我们想访问它的父节点,依旧只需要把 (子节点的下标 - 1) / 2 即可 依旧是 3

1.3 堆为什么物理结构上要用数组?

  • 事实上学习堆是为了学习堆排序打基础,在堆排序中,有时候需要频繁交换头尾节点,如果用数组,找节点就会方便很多,交换函数也很好写,效率会更高,用链表要不断去遍历,或者专门写个尾指针妥协,很没必要
  • 其次,如果我们用链式存储的话,访问子/父节点需要定义3个指针,需要多开辟很多空间
  • 堆一定是完全二叉树,用数组存放会很方便,其中不会有空节点,所有数据存储都是连续的

1.4 堆数据上的特点

  • 堆必须要始终满足满足:父节点值比子节点小或者父节点始终比子节点大
  • 我们称父节点值始终比子节点小的堆为小堆/小根堆
  • 我们称父节点值始终比子节点大的堆为大堆/大根堆

例如:
1.大堆:
在这里插入图片描述

2.小堆:
在这里插入图片描述

2 堆的实现

2.1 堆类型定义

//堆在物理上是一个数组,我们直接按数组的定义方式就行
//类型定义
typedef int HPDataType;

typedef struct Heap 
{
	HPDataType* data;
	int size;
	int capa;
}Heap;

2.2 需要实现的接口

//交换函数
void Swap(HPDataType* x, HPDataType* y);

//向上调整(小堆)
void AdjustUp(HPDataType* data, int child);

//向下调整(小堆)
void AdjustDown(HPDataType* data, int size, int father);

//初始化堆
void HPInit(Heap* php);

//销毁堆
void HPDestroy(Heap* php);

//堆插入
void HPPush(Heap* php, HPDataType x);

//堆删除
void HPPop(Heap* php);

//堆顶
HPDataType HPTop(Heap* php);

//堆判空
bool HPEmpty(Heap* php);

2.3 初始化堆

//像顺序表一样初始化就行
//初始化堆
void HPInit(HP* php)
{
	assert(php);
	php->a = (HPdatatype*)calloc(4, sizeof(HPdatatype));
	if (php->a == NULL)
	{
		perror("HPInit::calloc fail");
		exit(1);
	}
	php->capa = 4;
	php->size = 0;
}

2.4 销毁堆

//同样,像顺序表一样销毁就行
//销毁堆
void HPdestory(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->capa = 0;
	php->size = 0;
}

2.5 堆判空

//堆判空
bool HPEmpty(HP* php)
{
	assert(php);   //判空
	return php->size == 0;    //size是0就返回true
}

2.6 交换函数

//只是完成数据在空间上的交换
//交换函数
void Swap(HPdatatype* x, HPdatatype* y)
{
	HPdatatype tmp = *x;
	*x = *y;
	*y = tmp;
}

2.7 向上调整(小堆)

  • 注意这里是重点
  • 向上调整会在很多地方用到，基本思想就是让本应该在上面的节点往上挪
//向上调整(小堆)
void AdjustUp(HPdatatype* a, int child)
{
	assert(a);//判空

	int father = (child - 1) / 2;//推算出父节点的位置
	while (father < child && a[father] > a[child])      //只要子节点比父节点还小，就让子节点和父节点交换
	{								               		//重复此步骤直到子节点大于父节点或者子节点和自己比较
		Swap(&a[child], &a[father]); 
		child = father;
		father = (child - 1) / 2;
	}
}

请添加图片描述

2.8 向下调整(小堆)

  • 注意这里是重点
  • 向下调整同样会在很多地方用到
//向下调整(小堆)
void AdjustDown(HPdatatype* a, int size, int father)
{
	assert(a);//判空

	int child = (father * 2) + 1;      //先假设比较小的是左子节点
	if (child + 1 < size && a[child] > a[child + 1])        //如果右子节点比左子节点大,注意要判断一下子节点是否会超范围
	{
		child++;        //把child改成右子节点
	}
	while (child < size && a[father] > a[child] )    //如果父节点一直比子节点大就不断交换下移
	{                                                //直到子节点超出size范围或者父节点比子节点小就停下
		Swap(&a[father], &a[child]);     //交换

		father = child;              //重新找到父节点(交换后的父节点应该是原来的子节点的位置)
		child = (father * 2) + 1;    //重新定位子节点
		if (child + 1 < size && a[child] > a[child + 1])    //如法炮制
		{
			child++;
		}
	}
}

请添加图片描述

2.9 堆插入

  • 堆插入一般插入到末尾,因为末尾很空,啥也没有,比较好插入,插在其他地方还得先挪动才可以插入
//堆插入
void HPPush(HP* php, HPdatatype x)
{
	assert(php);   //判空

	//堆扩容,这里像数组一样扩容就行
	if (php->capa == php->size)
	{
		HPdatatype* tmp = (HPdatatype*)realloc(php->a, 2 * php->size * sizeof(HPdatatype));
		if (tmp == NULL)
		{
			perror("HPPush::realloc fail");
			exit(1);
		}
		php->a = tmp;
		php->capa *= 2;
	}

	php->a[php->size] = x;    //将要插入的数据放到堆低
	
	AdjustUp(php->a, php->size);      //通过向上调整找到这个数据本应该在的位置

	php->size++;      //别忘了让size++
}

2.10 堆删除

  • 堆删除一般删除堆顶的数据,但不能简单地把堆顶置为空,而是要和末尾数据交换,再一点点下调
//堆删除
void HPPop(HP* php)
{
	assert(php);     //判空
	if (!HPEmpty(php))    //如果堆不是空堆
	{
		Swap(&php->a[0], &php->a[php->size - 1]);   //交换堆顶和末尾的数据

		AdjustDown(php->a, php->size - 1, 0);    //将堆顶的数据向下挪到合适的位置

		php->size--;   //别忘了size--
	}
}

2.11 //堆顶

//取堆顶
HPdatatype HPTop(HP* php)
{
	assert(php);    //判空
	return HPEmpty(php) ? -1 : php->a[0];   //返回堆顶数据
}
  • 完整代码在最下面哦

佬!都看到这了,如果觉得有帮助的话一定要点赞啊佬 >v< !!!
放个卡密在这,感谢各位能看到这儿啦!
请添加图片描述

3 完整代码

3.1 heap.h

#pragma once

//头文件声明
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

//类型定义
typedef int HPdatatype;

typedef struct Heap
{
	HPdatatype* a;
	int size;
	int capa;
}HP;

//函数申明

//交换函数
void Swap(HPDataType* x, HPDataType* y);

//向上调整(小堆)
void AdjustUp(HPDataType* data, int child);

//向下调整(小堆)
void AdjustDown(HPDataType* data, int size, int father);

//初始化堆
void HPInit(Heap* php);

//销毁堆
void HPDestroy(Heap* php);

//堆插入
void HPPush(Heap* php, HPDataType x);

//堆删除
void HPPop(Heap* php);

//堆顶
HPDataType HPTop(Heap* php);

//堆判空
bool HPEmpty(Heap* php);

3.2 heap.c

#include "heap.h"

//初始化堆
void HPInit(HP* php)
{
	assert(php);
	php->a = (HPdatatype*)calloc(4, sizeof(HPdatatype));
	if (php->a == NULL)
	{
		perror("HPInit::calloc fail");
		exit(1);
	}
	php->capa = 4;
	php->size = 0;
}

//销毁堆
void HPdestory(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->capa = 0;
	php->size = 0;
}

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

//取堆顶
HPdatatype HPTop(HP* php)
{
	assert(php);
	return HPEmpty(php) ? -1 : php->a[0];
}

//交换
void Swap(HPdatatype* x, HPdatatype* y)
{
	HPdatatype tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整(小堆)
void AdjustUp(HPdatatype* a, int child)
{
	assert(a);

	int father = (child - 1) / 2;
	while (father < child && a[father] > a[child])
	{
		Swap(&a[child], &a[father]);
		child = father;
		father = (child - 1) / 2;
	}
}

//堆插入
void HPPush(HP* php, HPdatatype x)
{
	assert(php);

	//堆扩容
	if (php->capa == php->size)
	{
		HPdatatype* tmp = (HPdatatype*)realloc(php->a, 2 * php->size * sizeof(HPdatatype));
		if (tmp == NULL)
		{
			perror("HPPush::realloc fail");
			exit(1);
		}
		php->a = tmp;
		php->capa *= 2;
	}

	php->a[php->size] = x;
	
	AdjustUp(php->a, php->size);

	php->size++;
}

//向下调整(小堆)
void AdjustDown(HPdatatype* a, int size, int father)
{
	assert(a);

	int child = (father * 2) + 1;
	if (child + 1 < size && a[child] > a[child + 1])
	{
		child++;
	}
	while (child < size && a[father] > a[child] )
	{
		Swap(&a[father], &a[child]);

		father = child;
		child = (father * 2) + 1;
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
	}
}

//堆删除
void HPPop(HP* php)
{
	assert(php);
	if (!HPEmpty(php))
	{
		Swap(&php->a[0], &php->a[php->size - 1]);

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

		php->size--;
	}
}

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

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

相关文章

若依解决使用https上传文件返回http路径问题

若依解决使用https上传文件返回http路径问题

若依通过HTTPS请求进行文件上传时却返回HTTP的文件链接地址&#xff0c;主要原因是使用了 request.getRequestURL 获取链接地址。 解决办法&#xff1a; 在nginx配置文件location处加上&#xff1a;proxy_set_header X-Forwarded-Scheme $scheme; 然后代码通过request.getHea…
阅读更多...
【跳坑日记】暴力解决Ubuntu SSH报错： Failed to start OpenBSD Secure Shell server

【跳坑日记】暴力解决Ubuntu SSH报错： Failed to start OpenBSD Secure Shell server

报错环境说明&#xff1a; 服务器环境&#xff1a;Ubuntu 20.04 错误内容 最近服务器突然报错&#xff0c;提示如下图信息&#xff1a; 搜素了各种问答&#xff0c;国内的回答大多数是用 ssh-keygen -A命令来解决&#xff0c;但最终也无法登录服务器。 最终搜索到ask ubun…
阅读更多...
比较kube-proxy模式：iptables还是IPVS？

比较kube-proxy模式：iptables还是IPVS？

kube-proxy是任何 Kubernetes 部署中的关键组件。它的作用是将流向服务&#xff08;通过集群 IP 和节点端口&#xff09;的流量负载均衡到正确的后端pod。kube-proxy可以运行在三种模式之一&#xff0c;每种模式都使用不同的数据平面技术来实现&#xff1a;userspace、iptables…
阅读更多...
go-zero 实战（3）

go-zero 实战（3）

引入 Redis 在之前的 user 微服务中引入 redis。 1. 修改 user/internal/config/config.go package configimport ("github.com/zeromicro/go-zero/core/stores/cache""github.com/zeromicro/go-zero/zrpc" )type Config struct {zrpc.RpcServerConfMys…
阅读更多...
代码随想录算法训练营第36期DAY35

代码随想录算法训练营第36期DAY35

DAY35 122买卖股票的最佳时机ii 很巧妙&#xff0c;也很难想到&#xff1a;计算每天的利润&#xff08;今天卖出&#xff0c;昨天买入的利润&#xff09;&#xff0c;只取正数相加。 class Solution {public: int maxProfit(vector<int>& prices) { int…
阅读更多...
【机器学习300问】93、到底什么是优化器optimizer？

【机器学习300问】93、到底什么是优化器optimizer？

本文是对之前我写的梯度下降优化算法相关内容进行一次简要总结。在学习PyTorch框架的过程中&#xff0c;会遇到“优化器”&#xff08;optimizer&#xff09;这个概念。我想用通俗易懂的方式&#xff0c;说说优化器到底是个什么东西&#xff0c;并在此基础上&#xff0c;将前文…
阅读更多...
Qt代码初识

Qt代码初识

文章目录 Qt代码初识1. Qt Hello World 程序1.1 使⽤ "按钮" 实现1.1.1 纯代码⽅式实现1.1.2 可视化操作实现 1.2 使⽤ "标签" 实现1.2.1 纯代码⽅式实现1.2.2 可视化操作实现 2. 项⽬⽂件解析2.1 .pro ⽂件解析2.2 widget.h ⽂件解析2.3 main.cpp ⽂件解析…
阅读更多...
SwanLab入门深度学习：BERT IMDB文本情感分类

SwanLab入门深度学习：BERT IMDB文本情感分类

基于BERT模型的IMDB电影评论情感分类&#xff0c;是NLP经典的Hello World任务之一。 这篇文章我将带大家使用SwanLab、transformers、datasets三个开源工具&#xff0c;完成从数据集准备、代码编写、可视化训练的全过程。 观察了一下&#xff0c;中文互联网上似乎很少有能直接…
阅读更多...
Apache Log4j Server 反序列化命令执行漏洞（CVE-2017-5645）

Apache Log4j Server 反序列化命令执行漏洞（CVE-2017-5645）

漏洞复现环境搭建请参考 http://t.csdnimg.cn/MxmId 漏洞版本 Apache Log4j 2.8.2之前的2.x版本 漏洞验证 &#xff08;1&#xff09;开放端口4712 漏洞利用 &#xff08;1&#xff09;ysoserial工具获取 wget https://github.com/frohoff/ysoserial/releases/download/v0…
阅读更多...
强化学习算法

强化学习算法

从上图看出&#xff0c;强化学习可以分成价值/策略、随机策略/确定策略、在线策略/离线策略、蒙特卡洛/时间差分这四个维度。这里分析了基础算法中除了在线策略/离线策略以外的其他维度。 &#xff08;一&#xff09;基础知识 一、基础概念 重点概念&#xff1a;状态S、动作A、…
阅读更多...
浏览器自动化~插件推荐Automa

浏览器自动化~插件推荐Automa

引言 作为一款现代浏览器&#xff0c;得自动化吧&#xff0c;自主完成那些日复一日的重复性任务&#xff0c;开启音乐啥的不在话下~。而你则可以专注于其他更有意义的事情&#xff0c;如享受音乐带来的愉悦。但如果你对编写脚本一窍不通&#xff0c;又该如何实现这一愿景呢&am…
阅读更多...
华为机考入门python3--（28）牛客28-素数伴侣

华为机考入门python3--（28）牛客28-素数伴侣

分类&#xff1a;质数、素数、贪心算法、矩阵 知识点&#xff1a; 素数里除了2&#xff0c;都是奇数 奇奇偶&#xff0c;偶&#xff0b;偶偶 对矩阵求和 sum(map(sum, matrix)) 查找元素 3 在列表中的索引 my_list.index(3) 题目来自【牛客】 质数又称素数&#xff0c;是指…
阅读更多...
一种综合评价及决策方法：层次分析法AHP

一种综合评价及决策方法：层次分析法AHP

大家好&#xff0c;层次分析法(Analytic Hierarchy Process&#xff0c;AHP)是一种多准则决策方法&#xff0c;它帮助决策者处理复杂的决策问题&#xff0c;将其分解成层次结构&#xff0c;然后通过两两比较来确定各个层次的因素之间的相对重要性。这种分析方式允许决策者对问题…
阅读更多...
【vue与iframe通讯】

【vue与iframe通讯】

vue 与 iframe 通讯 发送数据vue 向 iframe 发送数据iframe 向 vue 发送数据接收信息( vue & iframe 通用) 实现相互通讯通讯流程图实现代码vue 页面iframe页面iframe内部重定向访问地址,更新vue路由 代码下载 前言&#xff1a;vue嵌套iframe实现步骤 发送数据 vue 向 if…
阅读更多...
回溯算法05（leetcode491/46/47）

回溯算法05（leetcode491/46/47）

参考资料&#xff1a; https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html 491. 非递减子序列 题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;找出并返回所有该数组中不同的递增子序列&#xff0c;递增子序列中 至少有两个元素…
阅读更多...
微软开发者大会：编程进入自然语言时代、“AI员工”闪亮登场

微软开发者大会：编程进入自然语言时代、“AI员工”闪亮登场

当地时间周二&#xff0c;美国科技公司微软召开年度Build开发者大会。在CEO纳德拉的带领下&#xff0c;微软各个产品团队再一次展现出惊人的执行力&#xff0c;在发布会上又拿出了接近50个新产品或功能更新。 整场发布会持续了接近两个小时&#xff0c;在这里挑选了一些投资者…
阅读更多...
知识表示概述

知识表示概述

文章目录 知识表示研究现状技术发展趋势 知识表示 知识是人类在认识和改造客观世界的过程中总结出的客观事实、概念、定理和公理的集合。知识具有不同的分类方式&#xff0c;例如按照知识的作用范围可分为常识性知识与领域性知识。知识表示是将现实世界中存在的知识转换成计算机…
阅读更多...
Linux进程的地址空间

Linux进程的地址空间

Linux进程的地址空间 1. 前言 在编写程序语言的代码时&#xff0c;打印输出一个变量的地址时&#xff0c;这个地址在内存中是以什么形式存在的&#xff1f;一个地址可以存储两个不同的值吗&#xff1f; 运行以下代码&#xff1a; #include <stdio.h> #include <un…
阅读更多...
C#-根据日志等级进行日志的过滤输出

C#-根据日志等级进行日志的过滤输出

文章速览 概要具体实施创建Log系统动态修改日志等级 坚持记录实属不易&#xff0c;希望友善多金的码友能够随手点一个赞。 共同创建氛围更加良好的开发者社区&#xff01; 谢谢~ 概要 方便后期对软件进行维护&#xff0c;需要在一些关键处添加log日志输出&#xff0c;但时间长…
阅读更多...
vulhub——ActiveMQ漏洞

vulhub——ActiveMQ漏洞

文章目录 一、CVE-2015-5254(反序列化漏洞)二、CVE-2016-3088&#xff08;任意文件写入漏洞&#xff09;2.1 漏洞原理2.2 写入webshell2.3 写入crontab 三、CVE-2022-41678&#xff08;远程代码执行漏洞&#xff09;方法一方法2 四、CVE-2023-46604&#xff08;反序列化命令执行…
阅读更多...
最新文章

Copyright @ 2022~2023