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

007 数据结构_堆——“C”

前言

本文将会向您介绍关于堆Heap的实现

具体步骤

tips:本文具体步骤的顺序并不是源代码的顺序

typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;

初始化

void HeapCreate(Heap* hp, HPDataType* a, int n)
{hp->_a = NULL;hp->_size = 0;hp->_capacity = 0;
}

扩容

解析:扩容的逻辑很简单,没什么可讲的,要注意的点有这里不要使用malloc,当再次需要扩容的时候,malloc函数只会分配新的内存空间,不会复制原有内存空间的内容,realloc函数会在分配新的内存空间时,将原有内存内容复制到新的内存空间中,并释放原有空间内容
//扩容
void CheckCapacity(Heap* hp)
{
if (hp->_capacity == hp->_size)
{int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("malloc fail");return;}hp->_a = tmp;hp->_capacity = newcapacity;
}
}

判空

// 堆的判空
bool HeapEmpty(Heap* hp)
{assert(hp);return hp->_size == 0;
}

交换

解析:这里提供了一个swap函数用于向上调整和向下调整时交换数据

//交换
void swap(int* a, int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}

插入

每次插入的数据都会进行向上调整,将一串数据建成小堆/大堆

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{CheckCapacity(hp);hp->_a[hp->_size] = x;hp->_size++;Adjustup(hp->_a, hp->_size - 1);
}

向上调整

当插入数据时,注意每次插入一个数据都会向上调整(直到根结点)图中这里只是将结构画了出来助于理解,真实的情况中并不是向右边的堆图一样

在这里插入图片描述

以小堆为例,当a[child] <a[parent]就将二者交换,并将parent 赋值给child,并利用新的child计算出新的parent,这样的做法是可以向上进行调整。这里若是将a[child] <a[parent]变成a[child] >a[parent]就是大堆

//向上调整
void Adjustup(int* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){swap(a, &a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

删除

解析:需要删除堆顶的数据,但是如果挪动数据删除堆顶的数据,可能会导致可能会导致堆的性质不满足,影响堆的正确性和效率。因此需要交换堆顶与末尾的数据,再将末尾的数据删除,这样一来就可以删除掉堆顶的数据,但是有个问题:将堆尾的数据调整到了堆顶,需要进行向下调整
// 堆的删除 删除堆顶
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));swap(hp->_a, &(hp->_a[0]), &(hp->_a[hp->_size - 1]));--hp->_size;//向下调整AdjustDown(hp->_a, hp->_size, 0);
}

向下调整

解析:当我们删除堆顶数据的时候进行向下调整,n:堆的数据个数,利用parent计算出child下标

//向下调整
void AdjustDown(int* a, int n, int parent)
{//计算左child,相当于(child = leftchild)int child = parent * 2 + 1;//当逐步地向下调整,child会越来越大,child不能超过堆数据个数while (child < n){//向下调整的时候右child可能越界//找左右child小的那一个进行与a[parent]比较if (child + 1 < n && a[child + 1] < a[child]){//若是默认的child(leftchild) > a[child + 1]++child;}//可调整<(小堆)为>(大堆)if (a[child] < a[parent]){swap(a, &a[child], &a[parent]);//向下调整parent = child;child = parent * 2 + 1;}else{break;}}
}

销毁

// 堆的销毁
void HeapDestory(Heap* hp)
{free(hp->_a);hp->_a = NULL;hp->_capacity = 0;hp->_size = 0;
}

获取堆顶数据

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));return hp->_a[0];
}

获取个数

// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp->_size;
}

小结

本文的分享就到这里啦,如果本文存在疏漏或错误的地方还请您能够指出!

相关文章:

007 数据结构_堆——“C”

前言 本文将会向您介绍关于堆Heap的实现 具体步骤 tips&#xff1a;本文具体步骤的顺序并不是源代码的顺序 typedef int HPDataType; typedef struct Heap {HPDataType* _a;int _size;int _capacity; }Heap;初始化 void HeapCreate(Heap* hp, HPDataType* a, int n) {hp-&…...

zabbix的原理与安装

一、Zabbix介绍 1、zabbix 是什么&#xff1f; zabbix是一个开源的IT基础监控软件&#xff0c;能实时监控网络服务&#xff0c;服务器和网络设备的状态&#xff0c;如网络使用&#xff0c;CPU负载、磁盘空间等&#xff0c;主要是包括数据的收集、报警和通知的可视化界面zabbi…...

ReactNative中升级IOS 17版本Crash解决

ReactNative中升级IOS 17版本Crash解决 ReactNative中升级IOS 17版本Crash解决一、问题描述二、原因分析三、解决方案决策3.1 设置宽高为非零值3.2 使用新的UIGraphicsImageRenderer替换就版本的UIGraphicsBeginImageContext 四、可能使用到该API的三方库4.1 react-native-fast…...

MongoDB详解

一、MongoDB概述 MongoDB 是一个基于 分布式文件存储 的开源 NoSQL 数据库系统&#xff0c;由 C 编写的。MongoDB 提供了 面向文档 的存储方式&#xff0c;操作起来比较简单和容易&#xff0c;支持“无模式”的数据建模&#xff0c;可以存储比较复杂的数据类型&#xff0c;是一…...

【SpringCloud微服务全家桶学习笔记-服务注册zookeeper/consul】

SpringCloud微服务全家桶学习笔记 Eureka服务注册 gitee码云仓库 9.其他服务注册框架 &#xff08;1&#xff09;zookeeper安装与使用 zookeeper需安装在虚拟机上&#xff0c;建议使用CentOS&#xff0c;安装地址如下&#xff1a; zookeeper镜像源 选择第一个进入后下载ta…...

【滑动窗口】LCR 016. 无重复字符的最长子串

LCR 016. 无重复字符的最长子串 解题思路 窗口内的字符串就是不重复子串每次遇到新的字符 看看窗口内是否存在该字符 如果存在直接剔除 然后调整窗口左边界不存在 添加窗口内部 右边界 class Solution {public int lengthOfLongestSubstring(String s) {if(s.length() < …...

C++中将类成员函数作为变量传递给函数

假设类ClassName有一个成员函数 void ClassName::funcname(int);通过typedef定义一个类成员函数指针类型,参数和返回值类型都要与成员函数对应 typedef void (ClassName::*FuncPtr)(int); // 定义类成员函数指针获取到的参数就是 FuncPtr pf...

2024届数字IC设计秋招面经-鼎信

背景 985硕士&#xff0c;计算机科班&#xff0c;实验室做cpu设计和fpga算法加速&#xff0c;我做处理器安全方向&#xff0c;有项目。 投递 8.25 没有笔试&#xff0c;两轮面试&#xff0c;直接通知下周一面试&#xff0c;草草的准备了下。 一面 技术面 9.4 不到半小时 …...

【数据结构】二叉树的节点数,叶子数,第K层节点数,高度,查找x节点,判断是否为完全二叉树等方法

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

前馈神经网络(FFNN)和多层感知机(MLP)

多层感知器&#xff08;MLP, Multi-Layer Perceptron&#xff09;和前馈神经网络&#xff08;Feed-Forward Neural Network, FFNN&#xff09;是深度学习中两个经常被使用的术语&#xff0c;它们经常被互换使用。让我们详细地了解这两个术语&#xff1a; 多层感知器 (MLP): M…...

EasySwipeMenuLayout - 独立的侧滑删除

官网 GitHub - anzaizai/EasySwipeMenuLayout: A sliding menu library not just for recyclerview, but all views. 项目介绍 A sliding menu library not just for recyclerview, but all views. Recommended in conjunction with BaseRecyclerViewAdapterHelper Feature…...

优麒麟下载、安装、体验

下载 官网 优麒麟 点击增强版、或者基础版进行下载 虚拟机安装 选择镜像 修改名称和存储路径 设置为50G 下一步&#xff0c;点击完成 开启安装 设置语言 去掉下载更新选项 继续 点击restart now 输入密码 出现下图说明安装成功&#xff0c;可以畅快的使用了...

Appium混合页面点击方法tap的使用

原生应用开发&#xff0c;是在Android、IOS等移动平台上利用官方提供的开发语言、开发类库、开发工具进行App开发&#xff1b;HTML5&#xff08;h5&#xff09;应用开发&#xff0c;是利用Web技术进行的App开发。目前&#xff0c;市面上很多app都是原生和h5混合开发&#xff0c…...

求解灰度直方图,如何绘制灰度直方图(数字图像处理大题复习 P1)

文章目录 1. 画 X 轴2. 画直方图3. Complete 视频原链接 数字图像处理期末考试大题 B站链接 1. 画 X 轴 2. 画直方图 有几个 0 就在图上画多高&#xff0c;同理有几个 1 &#xff0c;X1 的地方就画多高 3. Complete 这里的情况比较平均&#xff0c;一般来说不会这么平均&a…...

8种结构型设计模式对比

一、适配器模式 简介 适配器模式是一种结构型设计模式&#xff0c;它用于将不兼容的接口转换为可兼容的接口。适配器模式允许两个不兼容的类能够协同工作&#xff0c;通过将一个类的接口转换为另一个类所期望的接口形式。这样就能够在不修改现有代码的情况下&#xff0c;使两…...

【PX4】Ubuntu20.04+ROS Noetic 配置PX4-v1.12.2和Gazebo11联合仿真环境【教程】

【PX4】Ubuntu20.04ROS Noetic 配置PX4-v-v1.12.2和Gazebo11联合仿真环境【教程】 文章目录 【PX4】Ubuntu20.04ROS Noetic 配置PX4-v-v1.12.2和Gazebo11联合仿真环境【教程】0. 安装UbuntuROS1. 安装依赖2. 安装QGC地面站3. 配置PX4-v1.12.23.1 安装PX43.2 测试PX4是否成功安装…...

msvcp120.dll丢失怎么办?(五种方法快速解决)

首先&#xff0c;让我们来了解一下msvcp120.dll这个文件。msvcp120.dll是一个动态链接库文件&#xff0c;它是Microsoft Visual C 2012 Redistributable Package的一部分。这个文件的作用是支持一些应用程序的运行&#xff0c;例如游戏、办公软件等。当我们在使用这些软件时&am…...

eslint写jsx报错

eslint写jsx报错 ChatGPT提示 在写JSX时&#xff0c;ESLint可能会报出一些语法错误&#xff0c;这些错误通常是由于ESLint默认配置中不支持JSX语法导致的。为了解决这些错误&#xff0c;我们需要在ESLint配置文件中启用对JSX语法的支持。 首先&#xff0c;需要安装eslint-pl…...

最新适合小白前端 Javascript 高级常见知识点详细教程(每周更新中)

1. window.onload 窗口或者页面的加载事件&#xff0c;当文档内容完全加载完成会触发的事件&#xff08;包括图形&#xff0c;JS脚本&#xff0c;CSS文件&#xff09;&#xff0c;就会调用处理的函数。 <button>点击</button> <script> btn document.q…...

积分值和面积、对称性

积分的基本含义要从积分符号说起&#xff0c;积分号含有加号的意思&#xff0c; ∫ a b f ( x ) d x \int ^b_af(x)dx ∫ab​f(x)dx可以理解为&#xff1a;区间[a,b]无限细分为无穷多个dx,无穷多个f(x)乘以dx的累积和。根据上面的描述&#xff0c;面积可以理解为 ∫ a b ∣ f (…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...