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

【数据结构】二叉树--顺序结构及实现 (堆)

目录

一 二叉树的顺序结构

二 堆的概念及结构

三 堆的实现

1 包含所有接口 (Heap.h)

2 初始化,销毁和交换(Heap.c)

3 向上调整(Heap.c)

4 插入(Heap.c)

​5 向下调整(Heap.c)

6 删除(Heap.c)

​7 打印(Heap.c)

8 返回堆顶(Heap.c)

9 判断是否为空(Heap.c)

10 测试(Test.c)


一 二叉树的顺序结构

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空 间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺 序存储在物理上是一个数组,在逻辑上是一颗二叉树。

二 堆的概念及结构

如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足: <= 且 <= ( >= 且 >= ) i = 0,1, 2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质: 堆中某个节点的值总是不大于或不小于其父节点的值;

堆总是一棵完全二叉树。

三 堆的实现

1 包含所有接口 (Heap.h)

#pragma once
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
#include<stdio.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//向上调整
void AdjustUp(HPDataType* a, int child);//向下调整
void AdjustDown(HPDataType* a, int n, int parent);//交换
void Swap(HPDataType* p1, HPDataType* p2);
//打印
void HeapPrint(HP* php);
//初始化
void HeapInit(HP* php);
//销毁
void HeapDestroy(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//返回堆顶
HPDataType HeapTop(HP* php);
//是否为空
bool HeapEmpty(HP* php);

2 初始化,销毁和交换(Heap.c)

#include"Heap.h"void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}//销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}//交换
void Swap(HPDataType* p1, HPDataType* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}

 3 向上调整(Heap.c)

  时间复杂度 O(logN)

//向上调整
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent])//如果建大堆 就改成 a[child] > a[parent]{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

 4 插入(Heap.c)

//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

5 向下调整(Heap.c)

  时间复杂度 O(logN)

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//找小的那个孩子if (child+1 < n && 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;}}
}

6 删除(Heap.c)

//删除
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

7 打印(Heap.c)

//打印
void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

8 返回堆顶(Heap.c)

//返回堆顶
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

9 判断是否为空(Heap.c)

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}//堆为空返回1 true
//堆不为空 返回0 false

10 测试(Test.c)

小堆情况(升序)

#include"Heap.h"int main()
{int a[] = { 2,3,5,7,4,6,8,65,100,70,32,50,60 };HP hp;HeapInit(&hp);for (int i = 0; i < sizeof(a) / sizeof(int); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);return 0;
}

但是这种排序方式有明显的缺陷

1、先有一个堆的数据结构

2、空间复杂度复杂度的消耗

所以我们可以改进一下 用真正的堆排序 堆排序有很多细节 所以放在后面一节讲

本节很基础 与栈的实现有很多相似之处 大家也可以看我之前对栈的讲解 以此加深印象

继续加油!

相关文章:

【数据结构】二叉树--顺序结构及实现 (堆)

目录 一 二叉树的顺序结构 二 堆的概念及结构 三 堆的实现 1 包含所有接口 (Heap.h) 2 初始化,销毁和交换&#xff08;Heap.c) 3 向上调整&#xff08;Heap.c) 4 插入&#xff08;Heap.c) ​5 向下调整&#xff08;Heap.c) 6 删除&#xff08;Heap.c) ​7 打印&#…...

适用于嵌入式单片机的差分升级通用库

转至&#xff1a;痞子衡嵌入式半月刊&#xff1a;第 81 期 1、mcu_bsdiff_upgrade - 适用于嵌入式单片机的差分升级通用库 mcu_bsdiff_upgrade 是一款适用于嵌入式单片机的差分升级库&#xff0c;通用所有单片机&#xff0c;如stm32、华大、复旦微、瑞萨等。适合嵌入式的差分升…...

Exposure Normalization and Compensation for Multiple-Exposure Correction 论文阅读笔记

这是CVPR2022的一篇曝光校正的文章&#xff0c;是中科大的。一作作者按同样的思路&#xff08;现有方法加一个自己设计的即插即用模块以提高性能的思路&#xff09;在CVPR2023也发了一篇文章&#xff0c;名字是Learning Sample Relationship for Exposure Correction。 文章的…...

Arduino驱动BMI160 6轴惯性运动传感器(惯性测量传感器篇)

目录 1、传感器特性 2、硬件原理图 3、控制器和传感器连线图 4、驱动程序...

数据挖掘实战(3):如何对比特币走势进行预测?

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…...

巴以冲突中暴露的摄像头正对安全构成威胁

巴以冲突爆发后&#xff0c;许多配置不当的安全摄像头正暴露给黑客活动分子&#xff0c;使其周遭人员面临巨大安全风险。 Cyber​​news 研究人员发现&#xff0c;在以色列至少有165 个暴露的联网 RTSP 摄像头&#xff0c;在巴勒斯坦有 29 个暴露的 RTSP 摄像头。在巴勒斯坦&am…...

【Redis】Redis性能优化:理解与使用Redis Pipeline

原创不易&#xff0c;注重版权。转载请注明原作者和原文链接 文章目录 Pipeline介绍原生批命令(MSET, MGET) VS PipelinePipeline的优缺点一些疑问Pipeline代码实现 当我们谈论Redis数据处理和存储的优化方法时&#xff0c;「 Redis Pipeline」无疑是一个不能忽视的重要技术。…...

前端全局工具函数utils.js/正则(持续更新)

1. 接口返回提示 // 接口返回提示requestCodeTips(code, msg) {// code错误码&#xff0c;msg提示信息let errorrMessage switch (Number(code)) {case 400:errorrMessage 错误请求break;case 401:errorrMessage 未授权,请重新登录break;case 403:errorrMessage 拒绝访问b…...

如何基于先进视频技术,构建互联网视频监控安全管理平台解决方案

一、建设思路 依托互联网&#xff0c;建设一朵云&#xff0c;实现各类二三类视频资源统一接入&#xff0c;实现天网最后100米、10米、1米的全域覆盖。 依托人工智能与互联网技术&#xff0c;拓展视频资源在政府、社会面等多领域的全面应用&#xff1b;建设与运营模式并存&…...

【React native】navigation 状态重置

reset The reset action allows to reset the navigation state to the given state. It takes the following arguments: 重置操作允许将导航状态重置为给定状态&#xff1a; navigation.reset({index: 1,routes: [{name: Home}],});参考链接: 官方文档 https://reactnavigat…...

2023全国大学生软件测试大赛开发者测试练习题99分答案(ScapegoatTree2023)

2023全国大学生软件测试大赛开发者测试练习题99分答案(ScapegoatTree2023) 题目详情题解代码(直接全部复制到test类中即可)提示:该题只需要分支覆盖得分即可,不需要变异得分 题目详情 题解代码(直接全部复制到test类中即可) package net.mooctest;import static org.…...

Centos8 openjdk升级

1、卸载旧版本 sudo dnf remove java-1.8.0-openjdk 2、搜索新版本 yum search java-11-openjdk3、安装新版本 dnf install java-11-openjdk.x86_644、验证新版本 java -version...

开启深度学习之门—《深度学习》

开启深度学习之门—《深度学习》 《深度学习》由Ian Goodfellow和Yoshua Bengio合著&#xff0c;以其前沿的内容和深入浅出的风格&#xff0c;成为了当今最受欢迎的人工智能教材之一。首先&#xff0c;让我们来了解一下这两位作者。Ian Goodfellow是一位备受瞩目的计算机科学家…...

优先调节阀位,条件调节阀位

控制对象的执行机构可能存在多个&#xff0c;举例&#xff0c;压力通过变频和翻板这两个执行机构调节。默认调节翻板。这里定义一个全局布尔变量 bfgflag 初始默认为0&#xff1b;优先调节翻板&#xff0c;当翻板处于极限阀位时&#xff0c;bfgflag 赋值为1&#xff0c;开始调节…...

oracle入门笔记六

一、索引&#xff08;index&#xff09; 1、索引的作用 索引是优化查询的一种&#xff0c;使得查询效率特别高&#xff0c;索引是优化存储&#xff0c;索引作用在字段上 2、什么样的字段适合建索引 a、经常被查询的字段 b、不能为空&#xff0c;不能重复 c、字段的值不会被经常…...

腾讯云优惠券种类、领取方法及使用教程分享

腾讯云是国内领先的云计算服务提供商&#xff0c;为用户提供丰富的云计算产品和服务。为了吸引更多用户使用腾讯云的产品和服务&#xff0c;腾讯云会定期推出各种优惠券活动。本文将为大家介绍腾讯云优惠券的种类、领取方法及使用教程。 一、腾讯云优惠券种类介绍 腾讯云优惠券…...

JavaScript使用类-模态窗口

**上节课我们为这个项目获取了一些DOM元素&#xff0c;现在我们可以继续&#xff1b;**这个模态窗口有一个hidden类&#xff0c;这个类上文我们讲了&#xff0c;他的display为none&#xff1b;如果我们去除这个hidden的话&#xff0c;就可以让这个模态窗口展现出来。如下 cons…...

【轻松玩转MacOS】外部设备篇

引言 在开始之前&#xff0c;我们先来了解一下为什么要连接外部设备。想象一下&#xff0c;你正在享受MacOS带来的便捷和高效&#xff0c;突然需要打印一份文件&#xff0c;但你发现打印机无法连接&#xff1b;或者你需要将手机投屏到电脑上&#xff0c;却不知道该如何操作。这…...

location rewrite

Nginx location 匹配的规则和优先级 Nginx常用的变量 rewrite: 重定向功能 Location 匹配 URI URI&#xff1a;统一资源的表示符&#xff0c;是一种字符串标识&#xff0c;用于标识抽象或者物理资源 先来巩固一些与location结合使用的正则表达式 正则表达式&#xff1a;匹…...

XLSX.utils.sheet_to_json()解析excel,给空的单元格赋值为空字符串

前言 今天用到XLSX来解析excel文件&#xff0c;调用XLSX.utils.sheet_to_json(worksheet)&#xff0c;发现如果单元格为空的话&#xff0c;解析出来的结果&#xff0c;就会缺少相应的key&#xff08;如图所示&#xff09;。但是我想要单元格为空的话&#xff0c;值就默认给空字…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...