数据结构:堆
堆的概念
1.堆是一个完全二叉树
2.小堆(任何一个父亲<=孩子),大堆(任何一个父亲>=孩子)
堆的结构
物理结构:数组
逻辑结构:二叉树

#pragma once
#include<assert.h>
#include<iostream>
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;// 堆的构建
void HeapInit(Heap* hp);
void HeapInitArray(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
#include"标头.h"
void HeapInit(Heap* hp)
{assert(hp);hp->_a = NULL;hp->_capacity = 0;hp->_size = 0;
}void HeapInitArray(Heap* hp, HPDataType* a, int n)// 一次性初始化堆,插入所有值
{assert(hp);hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);memcpy(hp->_a, a, sizeof(HPDataType) * n);
//第一个节点不用调,时间复杂度为O(n*logn)//for (int i = 1; i < n; i++)//向上调整建堆//{// AdjustUp(hp->_a, i);//}
//叶节点不用调(没有子节点),时间复杂度为O(N)for (int i = (hp->_size-1 - 1) / 2; i >= 0; i--)//向下调整建堆//(hp->_size-1 - 1) / 2第一个-1是下标,后面的-1和/2是求父节点的公式{AdjustDown(hp->_a, hp->_size, i);}
}void HeapDestory(Heap* hp)
{assert(hp);free(hp->_a);hp->_a = NULL;hp->_capacity = 0;hp->_size = 0;
}void Swap(HPDataType* px, HPDataType* py)
{HPDataType temp = *px;*px = *py;*py = temp;
}
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 HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->_size == hp->_capacity){size_t newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;HPDataType* temp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);if (temp == NULL){perror("realloc fail");return;}hp->_a = temp;hp->_capacity = newcapacity;}hp->_a[hp->_size] = x;hp->_size++;AdjustUp(hp->_a, hp->_size - 1);
}void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;//假设法选出小的孩子while (child < n){if (a[child + 1] < a[child] && child + 1 < n){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void HeapPop(Heap* hp)//删除堆顶的数据
{assert(hp);assert(hp->_size > 0);//不可以挪动覆盖来删除堆顶数据//问题1.挪动覆盖时间复杂度O(N)// 2.堆结构被破坏,父子变兄弟,兄弟变父子//因此可以将首尾数据交换,删除尾部数据,然后进行向下调整算法Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);hp->_size--;AdjustDown(hp->_a, hp->_size, 0);
}HPDataType HeapTop(Heap* hp)
{assert(hp);return hp->_a[0];
}int HeapSize(Heap* hp)
{assert(hp);return hp->_size;
}bool HeapEmpty(Heap* hp)
{assert(hp);return hp->_size == 0;
}
堆排序
堆排序的本质是利用堆的性质,取出堆顶的数(最大或最小),然后将堆顶换成第二小/大的数
void HpSort(HPDataType* a, int n)
{Heap hp;HeapInitArray(&hp, a, n);int i = 0;while (!HeapEmpty(&hp)){a[i++] = HeapTop(&hp);HeapPop(&hp);}HeapDestory(&hp);
}
当然,这样的排序存在一定的缺点:
1.空间复杂度为O(N),太大了
2.使用是需要有堆这个数据结构
为了节省空间,可以通过将原数组改造成堆来排序,
排列出升序的数组采取堆排序应当使用大堆,因为小堆的堆顶是最小的数,堆顶的数已经是最小的了,不能改了
因此需要其他的数重新组成一个新堆,但是原本的堆全部乱了,父子变兄弟等问题会出现,只能重新建堆,浪费了时间因此需要采用大堆
大堆的堆顶是最大的,因此可以进行首尾交换,最大值就在数组尾部了,然后不把最后一个数看作堆内的数,继续进行向下调整,就可以选出次大的数
//创建大堆的向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;//假设法选出小的孩子while (child < n){if (a[child + 1] > a[child] && child + 1 < n){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void HpSort(HPDataType* a, int n)
{//先将数组建堆,时间复杂度O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i)//调整叶子上一层(叶子(最后面)在最后,不需要调整){AdjustDown(a, n, i);}//int end = n - 1;//end为数组下标while (end > 0){Swap(&a[0], &a[end]);//交换首尾AdjustDown(a, end, 0);//将堆首下调--end;}
}int main()
{int a[9] = { 9,8,7,6,5,4,3,2,1 };HeapSort(a, 9);for (int i = 0; i < 9; i++){printf("%d ", a[i]);}return 0;
}

这样,一个简单的堆排序就完成了
相关文章:
数据结构:堆
堆的概念 1.堆是一个完全二叉树 2.小堆(任何一个父亲<孩子),大堆(任何一个父亲>孩子) 堆的结构 物理结构:数组 逻辑结构:二叉树 #pragma once #include<assert.h> #include<iostream> typedef int HPDataType; typedef struct Heap {HPDataType* _a;int…...
CSS中三栏布局的实现
三栏布局一般指的是页面中一共有三栏,左右两栏宽度固定,中间自适应的布局,三栏布局的具体实现: 利用绝对定位,左右两栏设置为绝对定位,中间设置对应方向大小的margin的值。 .outer {position: relative;h…...
Linux搭建我的世界(MC)整合包服务器,All the Mods 9(ATM9)整合包开服教程
Linux使用MCSM面板搭建我的世界(Minecraft)整合包服务器,MC开服教程,All the Mods 9(ATM9)整合包搭建服务器的教程。 本教程使用Docker来运行mc服,可以方便切换不同Java版本,方便安装多个mc服版本。 视频教程:https:…...
让数据在业务间高效流转,镜舟科技与NineData完成产品兼容互认
近日,镜舟科技与NineData完成产品兼容测试。在经过联合测试后,镜舟科技旗下产品与NineData云原生智能数据管理平台完全兼容,整体运行高效稳定。 镜舟科技致力于帮助中国企业构建卓越的数据分析系统,打造独具竞争力的“数据护城河”…...
2.1HTML5基本结构
HTML5实际上不算是一种编程语言,而是一种标记语言。HTML5文件是由一系列成对出现的元素标签嵌套组合而成,这些标签以<元素名>的形式出现,用于标记文本内容的含义。浏览器通过元素标签解析文本内容并将结果显示在网页上,而元…...
设置浏览器显示小于12px以下字体
问题 我们在项目开发过程中有时候会遇到设计师给的小于12px的字体,IE、火狐浏览器、移动端等小于12px的字号大小还是可以正常显示的,但是谷歌浏览器上显示字体最小为12px,css设置font-size:10px,运行代码显示结果仍然…...
web蓝桥杯真题:成语学习
代码: //TODO 点击文字后,在idiom从左到右第一个空的位置加上改文字 getSingleWord(val) {let index this.idiom.indexOf() //从左往右查询空字符串this.$set(this.idiom, index, val) //响应式更新 },// TODO 校验成语是否输入正确答案 confirm…...
外包干了5天,技术明显退步。。。。。
先说一下自己的情况,本科生,19年通过校招进入南京某软件公司,干了接近2年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了2年的功能测试&…...
Vue:自定义消息通知组件
一、效果描述 在JS中使用一个Message函数,弹出一个自定义的消息框。 效果体验:缓若江海凝清光 二、实现方式 1.新建一个消息组件 2.新建一个js文件,新建一个需要导出函数 3.在函数中新建一个Vue实例,并将消息组件挂载上去。…...
2023 收入最高的十大编程语言
本期共享的是 —— 地球上目前已知超过 200 种可用的编程语言,了解哪些语言在 2023 为开发者提供更高的薪水至关重要。 过去一年里,我分析了来自地球各地超过 1000 万个开发职位空缺,辅助我们了解市场,以及人气最高和收入最高的语…...
Github 2024-03-11 开源项目周报 Top15
根据Github Trendings的统计,本周(2024-03-11统计)共有15个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目4TypeScript项目3Jupyter Notebook项目3C#项目1HTML项目1CSS项目1Dart项目1Lua项目1Shell项目1Rust…...
【DAY10 软考中级备考笔记】数据结构 图
数据结构 图 3月11日 – 天气:晴 晚上无线网络突然不能用了,花费好久弄这个,耽误了一些时间 1. 图的定义 这里需要注意完全图的定义,以及完全图的边数 这里需要注意连通图和连通分量的概念。 2. 图的存储结构 图有两种存储结构&a…...
java-ssm-jsp基于java的餐厅点餐系统的设计与实现
java-ssm-jsp基于java的餐厅点餐系统的设计与实现 获取源码——》公主号:计算机专业毕设大全...
蓝桥杯(1):python排序
1 基础 1.1 输出 1.1.1 去掉输出的空格 print("Hello","World",123,sep"") print("hello",world,123,sep) print(hello,world,123) #输出结果 #HelloWorld123 #helloworld123 #hello world 123 1.1.2 以不同的方式结尾 print(&quo…...
SpringMVC请求、响应和拦截器的使用
SpringMVC请求 RequestMapping注解 RequestMapping注解的作用是建立请求URL和处理方法之间的对应关系 RequestMapping注解可以作用在方法和类上 1. 作用在类上:第一级的访问目录 2. 作用在方法上:第二级的访问目录 3. 细节:路径可以不编写…...
基于springboot+layui仓库管理系统设计和实现
基于 java springbootlayui仓库管理系统设计和实现 博主介绍:多年java开发经验,专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末获取…...
【开源-土拨鼠充电系统】鸿蒙 HarmonyOS 4.0+微信小程序+云平台
本人自己开发的开源项目:土拨鼠充电系统 ✍GitHub开源项目地址👉:https://github.com/cheinlu/groundhog-charging-system ✍Gitee开源项目地址👉:https://gitee.com/cheinlu/groundhog-charging-system ✨踩坑不易&am…...
[抽象]工厂模式([Abstract] Factory)——创建型模式
[抽象]工厂模式——创建型模式 什么是抽象工厂? 抽象工厂模式是一种创建型设计模式,让你能够保证在客户端程序中创建一系列有依赖的对象组时,无需关心这些对象的类型。 具体来说: 对象的创建与使用分离: 抽象工厂模…...
QT网络编程之实现UDP广播发送和接收
推荐一个不错的人工智能学习网站,通俗易懂,内容全面,作为入门科普和学习提升都不错,分享一下给大家:前言https://www.captainbed.cn/ai 一.UDP通信 1.QT中实现UDP通信主要用到了以下类:QUdpSocket、QHost…...
SSL VPN基础原理
目录 SSL ---安全传输协议(安全套接层)---TLS ----传输层安全协议 SSL的工作原理 SSL会话建立的过程 编辑 数据传输过程中的封装示意图 无客户端认证的过程 有客户端认证的过程 SSL VPN的核心技术---虚拟网关技术 服务器验证的点: 资源…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
