数据结构初阶(C语言)-二叉树-顺序表建堆

一,堆的概念与结构

       如果有⼀个关键码的集合K = {k0 , k1 , k2 , ...,kn−1 },把它的所有元素按完全⼆叉树的顺序存储方式存储,在⼀个⼀维数组中,并满足:,i=0,1,2...则称为小堆(或⼤堆)。将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。

堆具有以下性质:

1.堆中某个结点的值总是不大于或不小于其父结点的值
2.堆总是⼀棵完全二叉树。

这里我们说一下完全二叉树的性质:

       对于具有 n 个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有结点从0 开始编号,则对于序号为 i 的结点有:
1.若 i>0 ,i 位置结点的双亲序号:(i-1)/2 ,i=0,i 为根结点编号,无双亲结点。

2.若 2i+1<n ,左孩子序号: 2i+1 , 2i+1>=n 否则无左孩子。

3.若 2i+2<n ,右孩子序号: 2i+2 , 2i+2>=n 否则无右孩子。

二,堆的实现及

2.1堆的定义 

堆底层结构为数组,因此定义堆的结构为:

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

        由于堆在本质上是基于顺序表结构去实现的,所以接下来我们所介绍的实现内容重点介绍与顺序表的不同的地方,相同部分则直接给出代码。

2.2堆的初始化函数HeapInit与堆的空间容量检查函数HpCapacheck

void HeapInit(HP* php)
{assert(php);php->arr = NULL;php->capacity = php->size = 0;
}void HpCapacheck(HP* hp)
{if (hp->capacity == hp->size){int exchange = hp->capacity == 0 ? 4 : hp->capacity * 2;HeapDataType* tmp = (HeapDataType*)realloc(hp->arr, sizeof(HeapDataType)* exchange);if (tmp == NULL){perror("realloc:tmp");exit(1);}hp->arr = tmp;hp->capacity = exchange;}
}

 2.3交换结点数据函数Swap

void Swap(HeapDataType* x, HeapDataType* y)
{HeapDataType tmp = *x;*x = *y;*y = tmp;
}

2.4检查堆结构是否为空函数HeapEmpty

bool HeapEmpty(HP* hp)
{assert(hp);return (hp->size == 0);
}

2.5向队中插入数据函数HeapPush

void HeapPush(HP* hp, HeapDataType x)
{assert(hp);HpCapacheck(hp);hp->arr[hp->size] = x;AdjustUpHp(hp, hp->size);hp->size++;
}

     前面的检查空间函数这里我们需要引用,同时判断传过来的指针是否为有效指针,但这时由于我们的堆是一个完全二叉树,对于我们的顺序表插入数据一般是从尾部插入,所以我们这里就需要用到向上调整法来调整我们的新数据使源数据的堆结构不被破坏:

2.5.1向上调整法

void AdjustUpHp(HP* hp, int child)
{int parents = (child - 1) / 2;while (child > 0){if (hp->arr[parents] > hp->arr[child]){Swap(&hp->arr[parents], &hp->arr[child]);}else{break;}child = parents;parents = (child - 1) / 2;}
}

        这里我们的向上调整法主要借助了完全二叉树的性质,由于我们新插入的数据是从尾部插入的,那么他的数组对应下标即为size-1,我们是在push之后对size进行的++,所以这里传过去的size即为当前新数据的下标,此时(size-1)/2为当前结点对应的父结点,我们这里建的是小堆,所以于其父结点相比小了便要交换数据,但由于我们先前的堆已经是小堆了,所以只要这里孩子比父大,我们就直接跳出循环,否则继续向上调整。

2.6删除堆中数据函数HeapPop

void HeapPop(HP* hp)
{assert(hp && !HeapEmpty(hp));Swap(&hp->arr[hp->size - 1], &hp->arr[0]);hp->size--;AdjustDownHp(hp,0);
}

       对堆的数据删除是从堆的最顶端的数据开始的,所以我们为了最大程度上减轻删除数据后对堆的影响,这里我们可以直接将根结点的数据与堆的最后一个数据交换,这样在尾删就会最小程度的影响堆结构。当然,新的数据到最顶端后,还需要进行调整,恢复堆的结构:

2.6.1向下调整法

void AdjustDownHp(HP* hp, int parents)
{int child = parents * 2 + 1;while (child < hp->size){if (child + 1 < hp->size && hp->arr[child] > hp->arr[child + 1]){child++;}if (hp->arr[child] < hp->arr[parents]){Swap(&hp->arr[child], &hp->arr[parents]);parents = child;child = parents * 2 + 1;}else{break;}}
}

       由于我们最开始是从父结点(根结点)开始调整的,所以为了确保不越界访问,我们需要先确认当前父结点是否有右孩子,如果有,他与左孩子相比谁更小就让谁与父结点比较。最后如果两个IF条件均不成立,我们则跳出循环,这时我们的堆结构就恢复完毕了。

2.7向上/向下调整法直接建堆

       像上面添加删除的去建堆,有些许麻烦,但如果我们直接给一个现成的数组,并将其整理为堆,或许这样建堆会更简单,这里我们就需要用到我们上面介绍的向上向下建堆法。

2.7.1向下建堆法及其时间复杂度的推导

void adjustdownarr(int* arr, int parents, int size)
{int child = parents * 2 + 1;while(child < size){if (child + 1 < size && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parents]){Swap(&arr[child], &arr[parents]);parents = child;child = parents * 2 + 1;}else{break;}}
}

        先说向下调整建堆,这里我们这里传过去的parents为根结点,而size便是有效数据的总个数,这也是由我们向下调整法的特性而实现的,毕竟对每个结点进行向下调整后,它所附属的子树及其本身的所有数据会被调整,最后最小的值被放入当前树的根结点中。直到调整到最后一个子树时便可以成堆。

这时我们来计算向下建堆的时间复杂度:先分析

 

那么我们需要移动的总步数为:(使用错位相减法计算)

(2)-(1)化简可得:

据二叉树的性质可得:

所以我们最终计算出T (n) = n - log2 (n + 1) ≈ n,即向下建堆法的时间复杂度为O(N)。

2.7.2向上建堆法及其时间复杂度

       这里与向下建堆法的思想一致,但向上建堆是先从各个子树开始进行调整,到最后将所有的子树调整完毕得到成型的堆,向上建堆法的代码和时间复杂度的推导这里就不给出了,读者可以自行推导,最终求出来的时间复杂度为O(n ∗ log2 n)。。

       可见向上建堆法时间复杂度上劣于向下建堆法,由于我们实际上现在的电脑内存基本都很大,所以我们在写代码时,更重要的是时间复杂度而不是以前二者均需了。下篇文章我们介绍链式结构堆的相关内容,去体会下递归的暴力美学。

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

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

相关文章

Python爬虫实战案例(爬取图片)

爬取图片的信息 爬取图片与爬取文本内容相似&#xff0c;只是需要加上图片的url&#xff0c;并且在查找图片位置的时候需要带上图片的属性。 这里选取了一个4K高清的壁纸网站&#xff08;彼岸壁纸https://pic.netbian.com&#xff09;进行爬取。 具体步骤如下&#xff1a; …

Unity ShaderLab基础

[原文1] [参考2] 一 基础知识 1. 1 着色器语言分类: 语言说明HLSL基于 OpenGL 的 OpenGL Shading LanguageGLSL基于 DirectX 的 High Level Shading LanguageCGNVIDIA 公司的 C for GraphicShader LabUnity封装了CG,HLSL,GLSL的Unity专用着色器语言,具有跨平台,图形化编程,便…

Java面试八股之Spring boot的自动配置原理

Spring boot的自动配置原理 Spring Boot 的自动配置原理是其最吸引人的特性之一&#xff0c;它大大简化了基于 Spring 框架的应用程序开发。以下是 Spring Boot 自动配置的基本原理和工作流程&#xff1a; 1. 启动类上的注解 Spring Boot 应用通常会在主类上使用 SpringBoot…

react中路由跳转以及路由传参

一、路由跳转 1.安装插件 npm install react-router-dom 2.路由配置 路由配置&#xff1a;react中简单的配置路由-CSDN博客 3.实现代码 // src/page/index/index.js// 引入 import { Link, useNavigate } from "react-router-dom";function IndexPage() {const …

elasticsearch-7.3.1安装注意事项

elasticsearch-7.3.1安装注意事项 一、背景二、步骤1、查看原ES版本2、新环境服务器2.1、是否有elasticsearch2.2、安装elasticsearch2.3、配置参数2.4、启动elasticsearch2.5、设置密码 三、报错-问题总结1、jdk不适用2、bootstrap checks failed3、Address already in use4、…

栈和队列(C语言)

栈的定义 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原则。 压栈&#xff1a;…

20分钟上手新版Skywalking 9.x APM监控系统

Skywalking https://skywalking.apache.org/ Skywalking是专为微服务、云原生和基于容器的&#xff08;Kubernetes&#xff09;架构设计的分布式系统性能监控工具。 Skywalking关键特性 ● 分布式跟踪 ○ 端到端分布式跟踪。服务拓扑分析、以服务为中心的可观察性和API仪表板。…

【stm32项目】基于stm32智能宠物喂养(完整工程资料源码)

基于STM32宠物喂养系统 前言&#xff1a; 随着人们生活幸福指数的提高&#xff0c;越来越多的家庭选择养宠物来为生活增添乐趣。然而&#xff0c;由于工作等原因&#xff0c;许多主人无法及时为宠物提供充足的食物与水。为了解决这一问题&#xff0c;我设计了一款便捷的宠物喂…

linux C++ onnxruntime yolov8 视频检测Demo

linux C onnxruntime yolov8 视频检测Demo 目录 项目目录 效果 ​编辑CMakeLists.txt 代码 下载 项目目录 效果 ./yolov8_demo --help ./yolov8_demo -c2 -ptrue ./yolov8_demo -c1 -strue CMakeLists.txt # cmake needs this line cmake_minimum_required(VERSION 3…

vim gcc

vim 使用 vs filename 分屏 ctrl ww 切窗口 shift zz 快速提出vim vim配置 vim启动时自动读取当前用户的家目录的.vimrc文件 vim配置只影响本用户 其他用户观看同一文件不受影响 gcc指令 & c文件编译过程 动态库 静态库 & 链接方式 有相应库才能进行…

【机器学习】不同操作系统下如何安装Jupyter Notebook和Anaconda

引言 Jupyter Notebook 是一个非常流行的开源Web应用程序&#xff0c;允许你创建和共享包含代码、方程、可视化和解释性文本的文档 文章目录 引言一、如何安装Jupyter Notebook1.1 对于Windows用户1.2 对于macOS用户1.3 对于Linux用户&#xff1a; 二、如何安装Anaconda2.1 对于…

css气泡背景特效

css气泡背景特效https://www.bootstrapmb.com/item/14879 要创建一个CSS气泡背景特效&#xff0c;你可以使用CSS的伪元素&#xff08;:before 和 :after&#xff09;、border-radius 属性来创建圆形或椭圆形的“气泡”&#xff0c;以及background 和 animation 属性来设置背景…

基于 Electron+Vite+Vue3+Sass 框架搭建

技术参考 技术描述Electron一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。嵌入 Chromium 和 Node.jsElectron Forge用于打包和分发 Electron 应用程序的一体化工具。英文地址在此Vite前端构建工具Vue3用于构建用户界面的 JavaScript 框架vitejs/plugin-vueVite 插…

java基础-String

之前有很长时间没进行更新了&#xff0c;现在开始会重新进行java基础的学习&#xff0c;所以会开始进行java基础方面的更新&#xff0c;今天会进行string字符串的学习。 String在底层被final(声明的变量或者对象不可以扩展/改变)修饰&#xff0c;故其不可变。其底层采用的是字符…

springboot集成redis之字典缓存

什么是redis的字典缓存&#xff1f; Redis的缓存是Redis内部用于存储键值对数据结构的一种基础数据结构。在Redis中&#xff0c;所有的键值对都是通过字典这种数据结构来存储的。字典在Redis中扮演着核心角色&#xff0c;因为它不仅用于数据库中的键值对存储&#xff0c;还用于…

Postman设置全部请求都携带请求头,Postman如何一次性设置请求头、不需要一个请求一个请求去添加请求头

文章目录 一、问题描述二、解决办法三、应用场景 一、问题描述 现在我有 n 个接口测试&#xff0c;其中 n 个都需要携带一致的请求头&#xff08;其实一般都是携带 JWT 令牌&#xff09;&#xff0c;怎么办&#xff1f;我要一个一个写&#xff1f;如图&#xff1a; 二、解决办…

go语言Gin框架的学习路线(十)

目录 GORM的CRUD教程 查询 普通查询 定义 User 结构体 查询所有用户 查询第一个用户 总结 条件查询 内联条件 额外查询选项 高级查询 链式操作 Scopes 多个立即执行方法 GORM的CRUD教程 CRUD 是 "Create, Read, Update, Delete"&#xff08;创建、查询…

[经验] 驰这个汉字的拼音是什么 #学习方法#其他#媒体

驰这个汉字的拼音是什么 驰&#xff0c;是一个常见的汉字&#xff0c;其拼音为“ch”&#xff0c;音调为第四声。它既可以表示动词&#xff0c;也可以表示形容词或副词&#xff0c;意义广泛&#xff0c;经常出现在生活和工作中。下面就让我们一起来了解一下“驰”的含义和用法。…

以Zookeeper为例 浅谈脑裂与奇数节点问题

一、脑裂现象的定义与影响 脑裂&#xff08;split-brain&#xff09;是指在分布式系统中&#xff0c;因网络分区或其他故障导致系统被切割成两个或多个相互独立的子系统&#xff0c;每个子系统可能独立选举出自己的领导节点。这一现象在依赖中心领导节点&#xff08;如Elastic…

【Qt 】JSON 数据格式详解

文章目录 1. JSON 有什么作用?2. JSON 的特点3. JSON 的两种数据格式3.1 JSON 数组3.2 JSON 对象 4. Qt 中如何使用 JSON 呢&#xff1f;4.1 QJsonObject4.2 QJsonArray4.3 QJsonValue4.4 QJsonDocument 5. 构建 JSON 字符串6. 解析 JSON 字符串 1. JSON 有什么作用? &#x…