堆【数据结构C语言版】【 详解】

目录-笔记整理

  • 一、思考
  • 二、堆概念与性质
  • 三、堆的构建、删除、添加
    • 1. 构建
    • 2. 删除
    • 3. 添加
  • 四、复杂度分析
    • 4.1 时间复杂度
    • 4.2 空间复杂度
  • 五、总结

一、思考

设计一种数据结构,来存放整数,要求三个接口:
1)获取序列中的最值(最大或最小)
2)添加元素
3)删除最值(最大或最小)

分析:

1)如果使用无序的线性表来实现,则需要发现获取最值、删除最值都需要遍历全部数据,复杂度为O(n)
2)如果使用有序的线性表,则查找并删除最值是虽是O(1)级别,但插入一个元素要重新进行排序,最好情况也是O(n)
3)如果平衡二叉查找树实现,虽然查找、插入、删除复杂度是O(log<sub>2</sub>n)级别,但其实现程度复杂,功能多,对于仅实现三个接口来说是”大炮打蚊子“,得不尝失。而使用”堆“能很好实现三种接口,且时间复杂度较低,获取最大值O(1),添加、删除都为O(log<sub>2</sub>n)

(注:这里的堆不是内存模型里的”堆空间“,勿要混淆)

二、堆概念与性质

堆(Heap)是一种数据结构,物理存储采用顺序表,其元素必须满足的性质是:
{ k i ≤ k 2 i + 1 k i ≤ k 2 i 或 { k i ≥ k 2 i + 1 k i ≥ k 2 i \lbrace^{k_i \leq k_{2i}}_{k_i \leq k_{2i+1}} 或 \lbrace^{k_i \geq k_{2i}}_{k_i \geq k_{2i+1}} {kik2i+1kik2i{kik2i+1kik2i
我们称前者为小顶堆(或小根堆),后者为大顶堆(或大根堆)。观察发现,这和完全二叉树的性质5很一样,因此可以逻辑上理解堆为一棵完全二叉树。
例如:序列(5,7,6,9,8,10)满足小根堆的性质在这里插入图片描述
这棵完全二叉树的根元素又叫堆顶元素,也是序列中的最小值,因此,每次查找最小值只需要获取堆顶元素即可,添加一个元素后,需要对堆重新进行调整每个元素满足堆性质,成为一个新堆;删除元素就是堆顶元素出堆,然后重新调整元素位置,直到全部元素满足堆性质,成为一个新堆。

三、堆的构建、删除、添加

1. 构建

(以小顶堆为例)
如何使一个序列变成满足堆性质的序列,并且具有添加、删除、获取最值三大接口?需要思考两个问题
1)如何由该混乱的序列构建一个堆?
2)往堆里添加、删除(删除堆顶)元素后,如何调整剩余元素成为一个新的堆?

已知一个混乱序列(10,8,6,9,7,5),和一个空堆H,然后遍历序列,每遍历一个序列往空堆添加元素,既要考虑每个元素满足堆的性质,又要思考新添加的元素位置(放在 i i i的位置还是 i + 1 i+1 i+1的位置),发现这种代码逻辑很难实现。由堆的性质和完全二叉树的性质类似,把已知的混乱序列逻辑上形象的看成一个完全二叉树。那么问题就转化为如何把一个”混乱“的完全二叉树转变为一棵小根堆对于的完全二叉树
在这里插入图片描述

观察图发现,我们只需要从非叶子 ⌊ n / 2 ⌋ \lfloor n/2\rfloor n/2结点开始,以它为根,对其根以及根的所有后代元素进行调整使其成为一棵小根堆,直到 ⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor-1 n/21 ~ 1 1 1位置为根元素都调整完毕,构建堆完成。
如何调整?
在这里插入图片描述
(注:假设现在有一个小根堆序列,其对应的完全二叉树如上图所示)
1)堆顶元素输出或出堆,让表尾元素(11)覆盖(5)并删除表尾元素
2)根(11)和其左右孩子(7,6)中最小的比较,发现6比11小,则6和11交换位置,这时以11为根的子树继续调整,10比11小,则互换位置…直到叶子结点(若中途发现根比孩子中最小的还小,则操作结束,该棵子树已经调整好了)
知道了如何调整,那么堆的构建就是从非叶子 ⌊ n / 2 ⌋ \lfloor n/2\rfloor n/2结点为根的树进行调整,直到 ⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor-1 n/21 ~ 1 1 1位置为根的每棵树都调整一遍,即堆构建完成

typedef int HeapType;
//构建堆,传入一个无序序列和序列长度,时间复杂度为O(n)
HeadType* CreateHeap(HeapType *H,int length){//由无序序列 H构建堆,该序列从索引0开始 int s;for(s=length/2-1;s>=0;s--){//建立堆AdjustHeap(H,s,length);//调整函数}return H;
}//堆排序 ---O(nlogn)
void HeapSort(HeapType *H){int s;int top;//堆顶元素出堆,表尾元素覆盖堆顶(删除表尾元素,即空出表尾单元),原堆顶元素放在表尾for(s=length;s>1;s--){//进行length-1次出堆,直到堆中只剩一个元素(该元素的索引:0)top=H[0];H[0]=H[s-1];AdjustHeap(H,0,s-1);H[s-1]=top;} 
}

2. 删除

堆中的删除操作,就是删除堆顶元素,其步骤和上文的如何调整一致,其调整函数如下

void AdjustHeap(HeapType*H,int s,int len){	//s=len/2-1//保存以索引s位置元素为根,此时s位置的结点并不满足最小堆的性质,其//他所有结点(s到len-1)位置的结点满足小顶堆的性质 int rc=H[s];int i;for(i=2*s+1;i<len;i=2*i+1){//由完全二叉树的性质:孩子结点和双亲结点的索引关系(注:结点位置从索引0开始,因此i=2*s+1而不是i=2*s)if(i<len-1&&H[i]>H[i+1])i++;//索引i是s孩子中的最小元素的索引if(rc<=H[i]) break;//若索引s处的元素小于孩子中最小的一个,则调整结束H[s]=H[i];s=i;}H[s]=rc;
}

3. 添加

往堆中添加元素,就是先把新元素放在堆的末端,再对新元素结点执行向上的操作,即让其和双亲结点比较,若新元素结点小于双亲结点则它们互换位置,若互换后,再于其双亲比较、交换,直到整棵树的根结点(索引为0的元素),若中途遇到双亲小于新元素的,则执行向上的操作结束,添加完毕

void addElement(HeapType *H,HeapType e,int len){//注:这里假设数组长度大(不会越界),len是元素的个数int newIndex=len;//新元素的索引int i=(newIndex+1)/2-1;//i是新元素的双亲的索引int eElem=e;//暂存新元素for(i;i>=0;i=(i-1)/2{//向上执行到根(0号结点)if(tElem<H[i]){H[newIndex]=H[i];newIndex=i;}else{break;	}}H[newIndex]=eElem;
}

四、复杂度分析

4.1 时间复杂度

创建堆,是从非叶子结点 ⌊ n / 2 ⌋ \lfloor n/2\rfloor n/2位置的元素开始到根,要调整的内部结点总数有 ⌊ n / 2 ⌋ \lfloor n/2\rfloor n/2,这些结点分布在多个层次,而构建堆过程中,每次循环都要调用一次调整函数AdjustHeap(),其每次执行调整函,其中需要比较的次数和其结点所在的树中的层次到叶子结点的深度有关(最坏的情况下)。
推导过程如下:
假设已知现在有目标堆是一个满堆,即其对应结点总数为n=2h-1的完全二叉树(也是满二叉树),深度为h,根结点处于第1层。我们处于第h-1层的每个非叶子结点向下调整时最多比较一次,第h-2层的最多比较2次…,第一层的根结点则比较n-1次(注:这里没计入筛选孩子中最小值的那一次比较)。第一层结点数:21-1=1,第二层结点数:22-1…第h-1层的结点总数:2h-2,则总的比较次数S=可能比较抽象,如下表

树的层次结点数比较次数
第1层1h-1
第2层2h-2
第3层22h-3
h-12h-21

则总的比较次数:
S = ( h − 1 ) + 2 ∗ ( h − 2 ) + 2 2 ∗ ( h − 3 ) + . . . + 2 h − 3 ∗ 2 + 2 h − 2 ∗ 1 = 2 h − h − 1 S=(h-1)+2*(h-2)+2^2*(h-3)+...+2^{h-3}*2+2^{h-2}*1=2^h-h-1 S=(h1)+2(h2)+22(h3)+...+2h32+2h21=2hh1

又由于n = 2h - 1,即 h=log2(n+1),则代入上式中,S=n-h,即创建堆时总比较次数S为O(n)级。往往堆排序过程中,就包含建堆(O(n))和排序两个过程,后者每输出一个堆顶元素,则执行一次对根结点的调整(比较的次数规模:O(h)),即时间复杂度为:O(log2n),综合为:O(nlog2n)

4.2 空间复杂度

常数级:O(1)

五、总结

堆排序,在排序过程中使用常数个辅助单元,其建堆时间为O(n),之后执行n-1次对当前的根向下的操作,不管给定的初始序列是有序还是无序,其用堆来排序的最好、最坏、平均时间复杂度均为:O(nlog2n),同时它是一种不稳定的排序,虽然堆排序速度很快,和快速排序时间复杂度一个水平,但其速度却不如快速排序(和时间复杂度的常数因子有关)。快速排序虽然很快,但是最坏的情况下时间复杂度达到O(n2),空间复杂度达到O(n)
(注:一般说某排序算法时间复杂度是多少,通常指平均情况下的)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Thinkphp/Laravel旅游景区预约系统的设计与实现

目录 技术栈和环境说明具体实现截图设计思路关键技术课题的重点和难点&#xff1a;框架介绍数据访问方式PHP核心代码部分展示代码目录结构解析系统测试详细视频演示源码获取 技术栈和环境说明 采用PHP语言开发&#xff0c;开发环境为phpstudy 开发工具notepad并使用MYSQL数据库…

景联文科技入选《2024中国AI大模型产业图谱2.0版》数据集代表厂商

近日&#xff0c;大数据产业领域头部媒体数据猿携手上海大数据联盟联合发布了备受瞩目的《2024中国AI大模型产业图谱2.0版》。以大数据与AI为代表的智能技术为主要视角&#xff0c;聚焦全产业链&#xff0c;为业内提供更为专业直观的行业指导。 景联文科技凭借高质量数据集&…

基于大数据的学生体质健康信息系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…

Vue Mini基于 Vue 3 的小程序框架

新的小程序框架 https://vuemini.org/ Vue Mini 是一个基于 Vue 3 的小程序框架&#xff0c;它允许开发者利用 Vue 3 的强大功能来构建微信小程序。Vue Mini 的核心优势在于它的响应式系统和组合式 API&#xff0c;这些特性让开发者能够以一种更声明式、更高效的方式来编写和…

江科大笔记——新建工程

STM32的开发方式 目前STM32的开发方式主要有基于寄存器的方式、基于标准库的方式&#xff08;库函数的方式&#xff09;、基于HAL库的方式&#xff1a; 基于库函数的方式是使用ST官方提供的封装好的函数&#xff0c;通过调用这些函数来间接地配置寄存器。基于HAL库的方式可以…

【机器学习(七)】分类和回归任务-K-近邻 (KNN)算法-Sentosa_DSML社区版

文章目录 一、算法概念二、算法原理&#xff08;一&#xff09;K值选择&#xff08;二&#xff09;距离度量1、欧式距离2、曼哈顿距离3、闵可夫斯基距离 &#xff08;三&#xff09;决策规则1、分类决策规则2、回归决策规则 三、算法优缺点优点缺点 四、KNN分类任务实现对比&am…

【CKA】二、节点管理-设置节点不可用

2、节点管理-设置节点不可用 1. 考题内容&#xff1a; 2. 答题思路&#xff1a; 先设置节点不可用&#xff0c;然后驱逐节点上的pod 这道题就两条命令&#xff0c;直接背熟就行。 也可以查看帮助 kubectl cordon -h kubectl drain -h 参数详情&#xff1a; –delete-empty…

【COSMO-SkyMed系列的4颗卫星主要用途】

COSMO-SkyMed系列的4颗卫星主要用于提供一个多用途的对地观测平台&#xff0c;服务于民间、公共机构、军事和商业领域。以下是这4颗卫星的主要用途&#xff1a; 民防与环境风险管理&#xff1a; 卫星的高分辨率雷达图像可用于监测自然灾害&#xff0c;如地震、洪水、滑坡等&am…

【计算机网络】网络层详解

文章目录 一、引言二、IP 基础知识1、IP 地址2、路由3、IP报文4、IP报文的分片与重组 三、IP 属于面向无连接型四、IP协议相关技术1、DNS2、ICMP3、NAT技术4、DHCP 一、引言 TCP/IP的心脏是网络层。这一层主要由 IP 和 ICMP 两个协议组成。网络层的主要作用是“实现终端节点之…

Redis进阶篇 - 缓存穿透、缓存击穿、缓存雪崩问题及其解决方案

文章目录 1 文章概述2 缓存穿透2.1 什么是缓存穿透&#xff1f;2.2 缓存穿透的解决方法2.2.1 做好参数校验2.2.2 缓存无效Key2.2.3 使用布隆过滤器2.2.4 接口限流 3 缓存击穿3.1 什么是缓存击穿&#xff1f;3.2 缓存击穿的解决方法3.2.1 调整热点数据过期时间3.2.2 热点数据预热…

Postgresql怎么查询数据库中所有的表,odoo17数据库最依赖表整理

今天遇到了一个需求,需要梳理odoo中数据库表的分类,所以想要知道怎么查询当前数据库中所有的表,特此记录. 一个简单的SQL语句: select * from pg_tables;得到的结果如下: 显然这个有点杂乱,我们换一个SQL语句: select tablename from pg_tables where schemanamepublic不过…

软件测试学习笔记丨Mock的价值与实战

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/32331 一、Mock的价值与意义 1.1 简介 测试过程中&#xff0c;对于一些不容易构造或获取的对象&#xff0c;用一个虚拟的对象来替代它&#xff0c;达到相同的效果&#xff0c;这个虚拟的对象…

启动服务并登录MySQL9数据库

【图书推荐】《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;》-CSDN博客 《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;&#xff08;数据库技术丛书&#xff09;》(王英英)【摘要 书评 试读】- 京东图书 (jd.com) Windows平台下安装与配置MyS…

Activiti 工作流大致了解

一、什么是 Activiti 简而言之&#xff0c;就是系统的流程图&#xff0c;如&#xff1a;请假审批流程、账单审批流程等。 二、mysql与pom配置 mysql要使用jdbc:mysql://localhost:3306/activiti?autoReconnecttrue pom文件要添加关键依赖 <!--activiti核心依赖--> &…

makefile和CMakeLists/C++包管理器

make 大家可能会很奇怪&#xff0c;都什么年代了&#xff0c;还学makefile&#xff0c;cmake都有些过时了&#xff0c;为什么还要再学这个呢&#xff1f; 我是这么看待这个问题的&#xff0c;cmake跨平台性还是很有有优势的&#xff0c;有着多年积累的底蕴&#xff0c;借助大模…

IDE 使用技巧与插件推荐全面指南

目录 目录 常用IDE概述 Visual Studio Visual Studio Code IntelliJ IDEA PyCharm Eclipse IDE 使用技巧 通用技巧 Visual Studio 专属技巧 Visual Studio Code 专属技巧 IntelliJ IDEA 专属技巧 插件推荐 Visual Studio 插件 Visual Studio Code 插件 IntelliJ…

STM32 实现 UDP 广播通信

目录 一、引言 二、准备工作 1.硬件准备 2.软件准备 三、LWIP 协议栈的配置与初始化 1.添加 LWIP 源文件 2.配置 LWIP 3.初始化 LWIP 四.创建 UDP 广播套接字 1.创建 UDP 控制块 2.绑定本地端口 五、设置 UDP 广播选项 1.设置广播地址 2.设置广播选项 六、发…

防反接电路设计

方案1 串联二极管&#xff0c; 优点&#xff1a;成本低、设计简单 缺点&#xff1a;损耗大&#xff0c;P ui 方案2 串联自恢复保险丝 当电源反接的时候&#xff0c;D4导通&#xff0c;F2超过跳闸带你留&#xff0c;就会断开&#xff0c;从而保护了后级电路 方案3 H桥电路…

[数据集][目标检测]电力场景防震锤缺陷检测数据集VOC+YOLO格式705张1类别

重要说明&#xff1a;防震锤缺陷图片太难找&#xff0c;数据集里面存在大量单一场景图片&#xff0c;请仔细查看图片预览谨慎下载&#xff0c;此外数据集均为小目标检测&#xff0c;如果训练map偏低属于正常现象 数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径…

COMP 6714-Info Retrieval and Web Search笔记week2

tokenizer&#xff1a;分词器 右半部分&#xff1a;倒排索引 Westlaw AND&#xff08;&&#xff09;&#xff1a; 要搜索必须同时出现在文档中的两个或多个词语&#xff0c;请使用 AND&#xff08;&&#xff09;。例如&#xff0c;输入 narcotics & warrant&#x…