6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)
目录
一.堆(Heap)的基本介绍
二.堆的常用操作(以小根堆为例)
三.实现代码
3.1 堆结构定义
3.2 向下调整算法*
3.3 初始化堆*
3.4 销毁堆
3.4 向上调整算法*
3.5 插入数据
3.6 删除数据
3.7 返回堆顶数据
四.下篇内容
1.堆排序
2.TopK问题
一.堆(Heap)的基本介绍
了解堆之前我们要简单了解完全二叉树:
在二叉树中,我们使用指针来连接每一个结点,最后构成一颗二叉树。而堆是一种使用数组来表示完全二叉树。其满足以下两条规则。
1.堆中结点值总是大于或者小于其父结点的值。
2.堆总是一颗完全二叉树。
由此可以推出有两种堆:大根堆和小根堆。
大根堆:根节点的值最大。
小根堆:根节点的值最小。

在堆(二叉树)中,如果一个结点的下标为i
其父亲的结点的下标为 (i-1)/ 2
其左孩子结点的下标为 (i+1)*2 -1 即 i*2 +1
其右孩子结点的下标为 (i+1)*2 即 i*2 + 2
数组的下标由0开始,读者可根据下图进行理解

二.堆的常用操作(以小根堆为例)
//初始化堆
void HeapInit(Heap* php, DataType* arr, int n);//数组建堆主要依赖的算法(这个算法要求数组的左右子树都是小堆)
//小堆,使用向下调整算法
void Adjustdown(DataType* arr, int n, int root);//向上调整算法
void Adjustup(DataType* arr, int n, int root);//销毁堆
void HeapDestory(Heap* php);//插入数据
void HeapPush(Heap* php, DataType x);//删除数据
void HeapPop(Heap* php, DataType x);//求堆顶(根)数据
DataType HeadTop(Heap* php);//交换两个数据
void swap(DataType* p1, DataType* p2);
三.实现代码
3.1 堆结构定义
//以小根堆为例
typedef int DataType;
typedef struct Heap
{DataType* arr; //数组int capacity; //容量int size; //元素大小
}Heap;
3.2 向下调整算法*
小根堆使用该算法的前提是左右子树都为小根堆,大根堆的前提是左右子树都为大根堆
该算法是从根结点依次向下找到比自己小(或者大)的结点,然后进行交换。
最后就能将新插入的根节点放到相应的位置
调整规则:
小根堆:根节点每一次与孩子结点中较小的一个交换
大根堆:根节点每一次与孩子结点中较大的一个交换
如下图

代码如下(以小根堆为例)
//向下调整算法
void Adjustdown(DataType* arr, int n, int root)
{//1.小根堆,找出左右孩子中较小的结点int parent = root;int child = root * 2 + 1; //表示左孩子while (child < n){//找到右孩子,如果右孩子比左孩子小,让child++。注意必须存在右孩子才能这么做if (child + 1 < n && arr[child + 1] < arr[child]){child++;}//如果该孩子比父亲小,就要交换if (arr[child] < arr[parent]){swap(arr[child], arr[parent]);//向下继续调整parent = child;child = parent * 2 + 1;}else{//如果孩子比父亲大,交换结束break;}}
}
3.3 初始化堆*
初始化堆:将一个随机的数组(数组大小随机,元素大小也随机)转换为堆。
思路:
1.将一个数组拷贝到一个堆结构中
2.利用向下调整算法对整个数组进行调整,由于整个数组不能直接进行向下调整(左右子树不符合堆结构),所以我们使用向下调整算法堆 最后一个结点的父亲结点开始调整,然后依次对这个结点之前的结点开始调整。
3.最后得出完整的堆结构
流程图:

代码
//初始化堆
void HeapInit(Heap* hp, DataType* arr, int n)
{//开辟空间,大小为 DataType*nhp->arr = (DataType*)malloc(sizeof(DataType) * n);assert(hp->arr != nullptr);memcpy(hp->arr, arr, sizeof(DataType) * n);hp->size = n;hp->capacity = n;//拷贝好数据后,由于数据是随机的,所以我们使用调整算法建堆//我们从最后一个度为2的结点开始向前依次对每一个结点都进行向下调整//最后一个结点下标为 n-1 则其父亲结点为(n-1-1)/2for (int i = (n - 1 - 1) / 2; i > 0; i--){Adjustdown(hp->arr, hp->size, i);}
}
3.4 销毁堆
//销毁堆
void HeapDestory(Heap* php)
{assert(php);free(php->arr);php->arr = NULL;php->size = 0;php->capacity = 0;
}
3.4 向上调整算法*
当我们插入新数据时,这个数据会破坏堆结构(如插入到数组末尾),所以我们需要向上调整
和向下调整算法类似
思路:
让新增节点依次和自己的父亲比较,然后交换即可
小根堆:比父亲小,交换。直到比父亲大就结束
大根堆:比父亲大,交换。直到比父亲小就结束
流程图:

代码
//向上调整算法,以小根堆为例
void Adjustup(DataType* arr, int n, int child)
{int parent = (child - 1) / 2;while (child > 0){if (arr[child] < arr[parent]){swap(arr[child], arr[parent]);//继续向上调整child = parent;parent = (child - 1) / 2;}else{break;}}
}
3.5 插入数据
//插入数据
void HeapPush(Heap* hp, DataType x)
{assert(hp);//1.增容if (hp->size == hp->capacity){hp->capacity *= 2;DataType* tmp = (DataType*)realloc(hp->arr, sizeof(DataType) * hp->capacity);assert(tmp != NULL);hp->arr = tmp;}//2.在数组的插入数据hp->arr[hp->size] = x;hp->size++;//对数组进行向上调整,将小的数据向上调整Adjustup(hp->arr, hp->size, hp->size - 1);
}
3.6 删除数据
删除堆顶的数据
我们交换第一个数据和最后一个数据,然后删除最后一个数据。再对堆顶进行向下调整
这样就能满足删除后,整个堆还是满足规则的
//删除数据(删掉堆顶的数据)
//类似于堆排序,交换第一个和最后一个数据。保证根节点的左右子树都是小根堆
void HeapPop(Heap* hp)
{assert(hp);assert(hp->arr);swap(hp->arr[0], hp->arr[hp->size - 1]);hp->size--;Adjustdown(hp->arr, hp->size, 0);
}
3.7 返回堆顶数据
直接返回0下标处的数据即可
//求堆顶(根)数据
DataType HeadTop(Heap* hp)
{assert(hp);assert(hp->size > 0);return hp->arr[0];
}
四.下篇内容
1.堆排序
2.TopK问题
相关文章:
6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)
目录 一.堆(Heap)的基本介绍 二.堆的常用操作(以小根堆为例) 三.实现代码 3.1 堆结构定义 3.2 向下调整算法* 3.3 初始化堆* 3.4 销毁堆 3.4 向上调整算法* 3.5 插入数据 3.6 删除数据 3.7 返回堆顶数据 四.下篇内容 1.堆排序 2.TopK问题 一…...
【智能终端】HBuilder X 与微信开发者工具集成与调试实战
目录 1. 需求和理解库、框架、平台 1.1 需求 1.2 理解 2.3 库、框架、平台 2.3.1 库(Library) 2.3.2 框架(Framework) 2.3.3 平台(Platform) 2.3.4 总结 2. 使用 HBuilder X 创建第一个 uni-app 应…...
结构体的字节对齐方式(__attribute_pack(packed))#pragma pack())
结构体的字节对齐方式(__attribute_pack(packed))&#pragma pack()) 1、编译器的字节对齐方式 当前编译器都有默认的字节对齐方式, struct PackedStruct {char a;int b;short c; };如上代码段中的结构体,在编译运行后发现他的大小并不…...
若依Ruoyi之智能售货机运营管理系统(新增运营运维工单管理)
idea抽取独立方法快捷键:ctrlaltm TaskDto.java package com.dkd.manage.service.impl;import java.time.Duration; import java.util.List; import java.util.stream.Collectors;import cn.hutool.core.bean.BeanUtil; import cn.hutool.core.collection.CollUti…...
ModuleNotFoundError: No module named ‘keras.layers.core‘怎么解决
问题 ModuleNotFoundError: No module named keras.layers.core,如图所示: 如何解决 将from keras.layers.core import Dense,Activation改为from tensorflow.keras.layers import Dense,Activation,如图所示: 顺利运行…...
C++(三)----内存管理
1.C/C内存分布 看下面这个问题(考考你们之前学的咋样): int globalVar 1; static int staticGlobalVar 1; void Test() {static int staticVar 1;int localVar 1;int num1[10] {1, 2, 3, 4};char char2[] "abcd";char* pCh…...
使用 ShuffleNet 模型在 CIFAR-100 数据集上的图像分类
简介 在深度学习领域,图像分类任务是衡量算法性能的重要基准。本文将介绍我们如何使用一种高效的卷积神经网络架构——ShuffleNet,来处理 CIFAR-100 数据集上的图像分类问题。 CIFAR-100 数据集简介 CIFAR-100 数据集是一个广泛使用的图像分类数据集&…...
怎么利用短信接口发送文字短信
在当今这个快节奏的数字时代,即时通讯已成为人们日常生活和工作中不可或缺的一部分。而短信接口(SMS Interface),作为传统与现代通讯技术结合的典范,凭借其高效、稳定、广泛覆盖的特性,在众多领域发挥着不可…...
【C#生态园】提升C#开发效率:掌握这六款单元测试利器
从xUnit到SpecFlow:C#测试驱动开发全指南 前言 在C#开发中,单元测试和模拟框架是至关重要的工具,它们可以帮助开发人员确保代码的质量和可靠性。本文将介绍一些常用的C#单元测试框架和相关库,包括xUnit、NUnit、Moq、FluentAsse…...
【QT】自制一个简单的小闹钟,能够实现语音播报功能
做了一个自制的小闹钟,能够自己输入时间,以及对应的闹铃,时间到了自动播放设定的闹铃,可以随时取消重新设定,采用分文件编译 注意:需要在.pro文件中加入:QT core gui texttospeech 代码…...
基于深度学习的图像描述生成
基于深度学习的图像描述生成(Image Captioning)是一种将计算机视觉与自然语言处理结合的任务,其目标是通过自动生成自然语言来描述输入的图像。该技术能够理解图像中的视觉内容,并生成相应的文本描述,广泛应用于视觉问…...
Linux和C语言(Day11)
一、学习内容 讲解有参函数 形参 和 实参 形参——定义时的参数,形式上的参数,没有实际意义,语法上必须带有数据类型 void fun(int a,int b); void fun(int a[],int n); void fun(char *s); 可以是:变量、数组、指针 实参——调用…...
使用Zlib库进行多文件或者多文件夹的压缩解压缩
zlib库可在git上自己clone下来然后使用cmake工具生成解决方案,编译、生成zlib二进制文件。然后将zlib库引入项目: //zlib库支持 #include "../zlib/include/zlib.h" #ifdef _DEBUG #pragma comment(lib, "../zlib/lib/zlibd.lib") …...
CSGHub携手Nvidia NIM、阿里计算巢打造企业级私有化部署解决方案
强强联合 人工智能与大数据的迅速发展,大模型的推理应用和资产管理已成为企业数字化转型的重要组成部分,企业正寻求高效、安全的AI模型部署解决方案。为应对日益增长的计算需求和复杂的数据管理挑战,CSGHub、Nvidia和阿里云计算巢强强联手&a…...
opencv的球面投影
cv::detail::SphericalProjector 在全景图像拼接任务中,可能需要对多个图像进行球面投影以实现无缝拼接。每个cv::detail::SphericalProjector可以负责一个图像的球面投影操作。通过将多个这样的投影器存储在std::vector中,可以对一组图像依次进行投影处…...
5. 去中心化应用(dApp)
去中心化应用(dApp) 去中心化应用(dApp)是基于区块链技术构建的应用程序,其核心特性是去中心化、透明和开放。dApp与传统应用有许多显著的区别,它们在实现和功能上都带来了新的变革。以下是对dApp的详细介…...
k8s服务发布Ingress
Kubernetes暴露服务的方式目前只有三种:LoadBlancer Service、NodePort Service、Ingress,通俗来讲,ingress和之前提到的Service、Deployment,也是一个k8s的资源类型,ingress用于实现用域名的方式访问k8s内部应用。 In…...
区块链学习笔记1--比特币
区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。 从狭义上来说:区块链是一种按照时间顺序将数据区块以顺序相连的方式组合成的一种链式数据结构,并以密码学的方式保证的不可篡改和不可伪造的分布式账本。 意思就是…...
在 Vite 项目中自动为每个 Vue 文件导入 base.less
在 Vue.js 项目中,使用 Less 作为 CSS 预处理器时,我们通常会创建一个全局的样式文件(如 base.less),用于存放一些全局变量、混合、通用样式等。为了避免在每个 Vue 组件中手动导入这个文件,我们可以通过配…...
RUST 学习之全局变量
RUST 全局变量 rust 全局变量编译期初始化的全局变量静态常量静态变量原子类型的静态变量 运行期初始化的全局变量lazy_staticBox::leakOnceCell & OnceLock 参考文档 rust 全局变量 编译期初始化的全局变量 静态常量 在编译期初始化,所以其赋值只能是表达式…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
