当前位置: 首页 > news >正文

【数据结构】堆(C语言)

今天我们来学习堆,它也是二叉树的一种(我滴神树!)
在这里插入图片描述

目录

  • 堆的介绍:
  • 堆的代码实现:
    • 堆的结构体创建:
    • 堆的初始化:
    • 堆的销毁:
    • 堆的push:
    • 堆的pop:
    • 判空 && 求Top元素 && 求size:
  • 完整源码:

堆的介绍:

如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足: <= 且
<= ( >= 且 >= ) i = 0,1,
2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

在这里插入图片描述

堆的代码实现:

堆的结构体创建:

typedef int HpDataType;typedef struct Heap
{int size;int capacity;HpDataType* a;
}Hp;

堆的初始化:

这里我们选择先不给赋值,等push时再给赋值

void HpInit(Hp* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

堆的销毁:

虽然与初始化相似,但是不能混用

void HpDestory(Hp* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}

堆的push:

我们需要一个向上调整算法:
在这里插入图片描述
这里我们选择创建小堆

因为我们只有push需要创建newnode,故不需要重新封装一个CreatNewnode函数调整算法时需要传的参数是

void HpPush(Hp* php, HpDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);HpDataType* tmp = (HpDataType*)realloc(php->a, sizeof(HpDataType)* newcapacity);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);
}

向上调整算法:

注意:
我们在进行向上传参时,要传入动态数组的地址和最后一个叶子节点的下标,为什么不是传入结构体的地址原因会在后来讲解

Swap(HpDataType* e1, HpDataType* e2)
{HpDataType tmp = *e1;*e1 = *e2;*e2 = tmp;
}void AdjustUp(HpDataType* a, int child)
{int parent = (child - 1) / 2;//假设进入循环时child > 0//这里选择child = 0作为结束标志是因为当child = 0时//a[child] 与 a[parent]已经交换过一次了,//他们两现在同时指向下标位0,不需要在交换了while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);}else{break;}child = (child - 1) / 2;parent = (parent - 1) / 2;}
}

堆的pop:

注意:
我们在进行pop时,并不是pop最后的叶子节点,这样没有实际意义,我们要pop的是根节点,这样是有实际意义的,比如Top k问题,堆排序

pop主体部分:

void HpPop(Hp* php)
{assert(php);Swap(&php->a[php->size - 1], &php->a[0]);php->size--;AdjustDown(php->a, php->size, 0);
}

同理我们也需要一个向下调整算法
在这里插入图片描述
注意:

传参时仍然是传动态数组a的地址,另外还需要size与根节点0的下标,
size用于判断是否超出堆的范围,0作为parent的初始值

向下调整时我们需要找出孩子节点中较大或较小的那个,在这种情况下我们可以使用假设法,假设后在进行判断是否正确,将两段逻辑变成一段逻辑

AdjustDown(HpDataType* a, int size, int parent)
{//假设法int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child] > a[child + 1]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);}else{break;}child = child * 2 + 1;parent = parent * 2 + 1;}
}

判空 && 求Top元素 && 求size:

bool HpEmpty(Hp* php)
{assert(php);return php->size == 0;
}int HpTop(Hp* php)
{assert(php);//注意为空assert(php->size);return php->a[0];
}int HpSize(Hp* php)
{assert(php);return php->size;
}

完整源码:

heap.c

#define _CRT_SECURE_NO_WARNINGS 1#include"heap.h"void HpInit(Hp* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void HpDestory(Hp* php)
{assert(php);free(php->a);php->a = NULL;php->size = 0;
}Swap(HpDataType* e1, HpDataType* e2)
{HpDataType tmp = *e1;*e1 = *e2;*e2 = 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]);}else{break;}child = (child - 1) / 2;parent = (parent - 1) / 2;}
}
//小堆
void HpPush(Hp* php, HpDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);HpDataType* tmp = (HpDataType*)realloc(php->a, sizeof(HpDataType)* newcapacity);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);
}AdjustDown(HpDataType* a, int size, int parent)
{//假设法int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child] > a[child + 1]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);}else{break;}child = child * 2 + 1;parent = parent * 2 + 1;}
}void HpPop(Hp* php)
{assert(php);Swap(&php->a[php->size - 1], &php->a[0]);php->size--;AdjustDown(php->a, php->size, 0);
}bool HpEmpty(Hp* php)
{assert(php);return php->size == 0;
}int HpTop(Hp* php)
{assert(php);assert(php->size);return php->a[0];
}int HpSize(Hp* php)
{assert(php);return php->size;
}

heap.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int HpDataType;typedef struct Heap
{int size;int capacity;HpDataType* a;
}Hp;void HpInit(Hp* php);void HpDestory(Hp* php);void HpPush(Hp* php, HpDataType x);void HpPop(Hp* php);bool HpEmpty(Hp* php);int HpSize(Hp* php);int HpTop(Hp* php);

有疑问可以及时找博主交流

相关文章:

【数据结构】堆(C语言)

今天我们来学习堆&#xff0c;它也是二叉树的一种&#xff08;我滴神树&#xff01;&#xff09; 目录 堆的介绍&#xff1a;堆的代码实现&#xff1a;堆的结构体创建&#xff1a;堆的初始化&#xff1a;堆的销毁&#xff1a;堆的push&#xff1a;堆的pop&#xff1a;判空 &am…...

使用 Raspberry Pi、Golang 和 HERE XYZ 制作实时地图

到目前为止&#xff0c;您可能已经看过我的一些与 Raspberry Pi 和位置数据相关的教程。我是这些小型物联网 (IoT) 设备的忠实粉丝&#xff0c;并编写了有关使用 Golang 进行 WLAN 定位 和 使用 Node.js 进行 GPS 定位的教程。 我想继续沿着 Golang 路线&#xff0c;做一个关于…...

贪吃蛇(c实现)(真的超级超级简单)

1.代码请看贪吃蛇c实现 王赫辰/c语言 - 码云 - 开源中国 (gitee.com) 2.本项目宗旨&#xff1a; 1.不引入复杂的库函数&#xff08;其他博主的全是陌生库函数看不懂&#xff1f;看我就对了&#xff01;◕‿◕&#xff09; 2.不使用c语法 &#xff08;都说了c实现&#xff0c;…...

linux 内存回收mglru算法代码注释2

mglru与原lru算法的兼容 旧的lru算法有active与inactive两代lru&#xff0c;可参考linux 内存回收代码注释&#xff08;未实现多代lru版本&#xff09;-CSDN博客 新的算法在引入4代lru的同时&#xff0c;还引入了tier的概念。 新旧算法的切换的实现在lru_gen_change_state&a…...

Exchange意外登录日志

最近在审计Exchange邮件系统的时候&#xff0c;发现大量用户半夜登录的日志。而且都是成功的&#xff0c;几乎没有失败的情况。其中Logon Type 8表示用户从网络登录。 Logon type 8: NetworkCleartext. A user logged on to this computer from the network. The user’s pas…...

NX二次开发UF_CURVE_ask_curve_turn_angle 函数介绍

文章作者&#xff1a;里海 来源网站&#xff1a;https://blog.csdn.net/WangPaiFeiXingYuan UF_CURVE_ask_curve_turn_angle Defined in: uf_curve.h int UF_CURVE_ask_curve_turn_angle(tag_t curve, double orientation [ 3 ] , double * angle ) overview 概述 Returns …...

UE 进阶篇一:动画系统

导语: 下面的动画部分功能比较全,可以参考这种实现方式,根据自己项目的颗粒度选择部分功能参考,我们商业项目动画部分也是这么实现的。 最后实现的效果如下: 最终效果 目录: ------------------------------------------- 文末有视频教程/工程地址链接 -------------…...

超文本传输协议

超文本传输协议&#xff08;HypertextTransfer Protocol&#xff0c;HTTP&#xff09;是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。它指定了客户端可能发送给服务器什么样的消息以及得到什么样的响应。请求和响应消息的头以ASCII形式给出&#xff1b;而消息内容…...

『heqingchun-Ubuntu系统+x86架构+编译安装ffmpeg+带有nvidia硬件加速』

Ubuntu系统x86架构编译安装ffmpeg带有nvidia硬件加速 一、准备文件 注&#xff1a;可直接下载我上传的CSDN资源&#xff0c;然后直接跳到"一"中的第"3"项"将文件按以下顺序存放"。 ffmpeg源码&#xff1a;音视频开发ffmpeg编译所需资源文件 其…...

UE5 UI教程学习笔记

参考资料&#xff1a;https://item.taobao.com/item.htm?spma21n57.1.0.0.2b4f523cAV5i43&id716635137219&ns1&abbucket15#detail 基础工程&#xff1a;https://download.csdn.net/download/qq_17523181/88559312 1. 介绍 工程素材 2. 创建Widget UE5 UI系统的…...

Leetcode:622. 设计循环队列 题解【具详细】

目录 一、题目&#xff1a; 二、思路详解&#xff1a; 1.循环队列的存储定义 2.循环队列的创建 3.循环队列的判空与判断情况 (1) 循环队列的判空: (2) 循环队列的判满 4.循环队列元素的插入 5.循环队列元素的删除 6.获取队头元素 7.获取队尾元素 8.循环队列释放 三…...

ArkTS基础知识 【习题】

判断题 1.循环渲染ForEach可以从数据源中迭代获取数据&#xff0c;并为每个数组项创建相应的组件。 正确(True) 2. Link变量不能在组件内部进行初始化。 正确(True) 单选题 1.用哪一种装饰器修饰的struct表示该结构体具有组件化能力&#xff1f;(A) A. Component B. Entry C…...

是否有无限提取的代理IP?作为技术你需要知道这些

最近有互联网行业的技术小伙伴问到&#xff0c;有没有可以无限提取的代理IP&#xff1f;就是比如我一秒钟提取几万、几十万次&#xff0c;或者很多台机器同时调用API提取链接&#xff0c;这样可以吗&#xff1f;看到这个问题&#xff0c;不禁沉思起来&#xff0c;其实理论上是存…...

【算法萌新闯力扣】:卡牌分组

力扣热题&#xff1a;卡牌分组 一、开篇 今天是备战蓝桥杯的第22天。这道题触及到我好几个知识盲区&#xff0c;以前欠下的债这道题一并补齐&#xff0c;哈希表的遍历、最大公约数与最小公倍数&#xff0c;如果你还没掌握&#xff0c;这道题练起来&#xff01; 二、题目链接:…...

深入解析:如何开发抖音票务小程序

当下&#xff0c;开发抖音票务小程序成为了吸引年轻用户群体的一种创新方式。本文将深入解析如何开发抖音票务小程序&#xff0c;探讨关键步骤和技术要点。 1.确定需求和功能 考虑到抖音的用户特点&#xff0c;可以加入与短视频相关的票务功能&#xff0c;如在线购票、观影记录…...

vue中 mixin用法

在Vue.js中&#xff0c;mixin是一种可以在多个组件之间共享Vue组件选项的灵活方式。mixin对象可以包含任何组件选项。当组件使用mixin时&#xff0c;所有mixin对象的选项将被“混合”到该组件的选项中。 使用mixin的一个主要优点是可以在多个组件之间重用和共享代码。这可以帮…...

Java入门基础:浅显易懂 while

文章目录 前言一、布尔表达式二、while三、语法四、示例 前言 在开发过程中不管是 while 语句还是其他语句都会经常用到布尔表达式&#xff0c;所以在学习 while 之前需要先明白什么是布尔表达式&#xff1f; 一、布尔表达式 布尔表达式只有2种结果&#xff1a;true / false 看…...

DNS/ICMP协议、NAT技术

目录 DNS协议DNS背景域名简介 ICMP协议ICMP功能ping命令traceroute命令 NAT技术NAT技术背景NAT IP转换过程NAPTNAT技术的缺陷NAT和代理服务器 网络协议总结应用层传输层网络层数据链路层 DNS协议 DNS&#xff08;Domain Name System&#xff0c;域名系统&#xff09;协议&…...

React整理总结(七、Hooks)

1.Class组件的优缺点 优点 class组件可以定义自己的state&#xff0c;用来保存组件自己内部的状态&#xff1b;函数式组件不可以&#xff0c;因为函数每次调用都会产生新的临时变量&#xff1b;class组件有自己的生命周期&#xff0c;我们可以在对应的生命周期中完成自己的逻…...

软件测试之银行测试详解

一、金融类软件测试 举个栗子&#xff0c;银行里的软件测试工程师。横向跟互联网公司里的测试来说&#xff0c;薪资相对稳定&#xff0c;加班的话想对来说没那么多&#xff08;有些银行加班也挺严重的&#xff09;&#xff0c;但业务稳定。实在是测试类岗位中的香饽饽&#xf…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...