二叉树:堆的建立和应用

在建立堆之前,我们要知道什么是树和二叉树

树是一种非线性的数据结构,它是由n(n>0)个结点组成的一个具有层次关系的集合,之所以把它叫做树,是因为它长得像一棵倒挂的树,也就是根在上面,叶子在下面

树形结构

树形结构的特性: 

1、树里面有一个特殊的结点,叫做根结点,它没有前驱结点

2、除了根结点以外的结点又分为m(m>0)个集合,其中每一个集合又是一棵与树结构类似的子树,而且每棵子树的根结点都有一个且只有一个前驱结点,但可以有多个或0个后继结点

3、在树形结构中,子树之间不能有交集,否则就不是树形结构

4、除了根结点,每个结点有且只有一个父结点

5、一棵n个结点的树有n-1条边

下面是一些与树相关的术语

⽗结点/双亲结点:若⼀个结点含有⼦结点,则这个结点称为其⼦结点的⽗结点
⼦结点/孩⼦结点:⼀个结点含有的⼦树的根结点称为该结点的⼦结点; 
结点的度:⼀个结点有⼏个孩⼦,他的度就是多少;
树的度:⼀棵树中,最⼤的结点的度称为树的度;
叶⼦结点/终端结点:度为 0 的结点称为叶结点
分⽀结点/⾮终端结点:度不为 0 的结点;
兄弟结点:具有相同⽗结点的结点互称为兄弟结点(亲兄弟);
结点的层次:从根开始定义起,根为第 1 层,根的⼦结点为第 2 层,以此类推;
树的⾼度或深度:树中结点的最⼤层次;
结点的祖先:从根到该结点所经分⽀上的所有结点
路径:⼀条从树中任意节点出发,沿⽗节点-⼦节点连接,达到任意节点的序列;
⼦孙:以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙;
森林:由 m m>0 ) 棵互不相交的树的集合称为森林;

非树形结构 

 树的表示

树的结构相比于线性表要复杂点,存储起来也会比较麻烦,又要保存值,又要保存结点与结点之间的关系

在这里我们用一种比较常用的表示方法:孩子兄弟表示法

struct TreeNode
{struct Node* child; // 左边开始的第⼀个孩⼦结点struct Node* brother; // 指向其右边的下⼀个兄弟结点int data; // 结点中的数据域
};

树形结构实际运用场景

⽂件系统是计算机存储和管理⽂件的⼀种⽅式,它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中,树结构被⼴泛应⽤,它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。

 

 二叉树

在树形结构中我们最常用的就是二叉树,一棵二叉树是结点的一个有限集合,这个集合是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成

二叉树的特点

1、二叉树不存在度大于2的结点;

2、二叉树的子树有左右之分,顺序不能颠倒,所以二叉树是一棵有序树

 当然二叉树的结构不单单就上面一种情况

 现实中也存在这种结构的树

特殊的二叉树:满二叉树、完全二叉树

满二叉树:一棵二叉树,如果每一层的结点数都达到最大值,则这棵二叉树就是满二叉树

比如一棵二叉树的层数为h,且它的结点总数是2^k-1,则它就是满二叉树

 完全二叉树:完全二叉树就是除了最后一层,其他层数的结点数都达到最大的一种二叉树,满二叉树是一种特殊的完全二叉树,完全二叉树是一种效率很高的数据结构

 二叉树的特性

1、当根结点的层数为1,则一棵非空二叉树的第h层上最多有2^(h-1)个结点

2、当根结点的层数为1,则深度为h的二叉树的总结点数为2^h-1;

3、当根结点的层数为1,结点数为n的满二叉树的深度h=log2(n+1)(以2为底,n+1为对数)

二叉树的存储结构 

二叉树可以使用两种结构存储:顺序存储、链式存储

我们在这里主要讲解二叉树的顺序结构存储,在前面数据结构的学习中我们得知顺序结构是使用数组来存储,而完全二叉树十分适用于顺序结构存储,因为这样不会有空间的浪费

而如果其他的二叉树使用顺序结构存储,就会造成空间的浪费

 在数据结构中,我们通常把堆(一种二叉树)使用顺序结构的数组来存储,但要注意的是这里堆和操作系统中的堆是两回事,一个是数据结构,一个是操作系统中内存管理内存的一块区域分段

概念

堆是一种特殊的二叉树,具有二叉树的特性的同时,还具备一些特性:堆分为大堆/大根堆、小堆/小根堆;我们把根结点最大的堆叫做大堆/大根堆把根结点最小的堆叫做小堆/小根堆

 堆的特性

1、结点下标为i(i>0)的父结点下标为:(i-1)/2,i=0就表示为根结点,它没有父结点;

2、结点下标为i(i>0)的左孩子下标为:2*i+1;右孩子下标为:2*i+2,当它们的i下标超过总结点数,就不存在孩子结点

 堆的实现

向上调整算法

堆的向上调整算法使用的前提是:在插入新元素之前,前面的元素就已经满足了堆的性质!!

它的本质思想(建小堆):

1、将新元素插入到叶子节点;

2、与它的父结点进行比较,如果小于父结点的值,就交换;

3、把原本父结点下标当作子结点,在进行步骤2,与现在下标的父结点进行比较,重复该步骤

结束条件结点到达根结点位置或者提前调整到合适的位置,满足了堆的特性

void Swap(int* x, int* y)
{int temp = *x;*x = *y;*y = temp;
}//向上调整算法
void AdjustUp(HPDataType* a, int child)
{assert(a);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;}}
}

向下调整算法

向下调整算法的前提是左右子树都符合堆的条件

它的本质思想(建小堆):

1、从根结点开始,与它的左右结点中较小的进行比较,如果小于子结点的值就交换值;

注:要考虑两个子结点的大小的比较,而且右孩子结点的下标不能大于总结点数

2、交换后的子结点作为父结点重复上面步骤

直到孩子结点下标大于或等于总结点数

//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int child = parent * 2 + 1;while (child<n){if (child+1 < n && a[child] > a[child + 1])//先找孩子结点{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

结构

堆是使用顺序结构存储的,所以它的结构和顺序表的结构相同

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

初始化和销毁

初始化和销毁也和顺序表一样

//初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}//销毁
void HPDestroy(HP* php)
{assert(php);if (php->arr){free(php->arr);}php->arr = NULL;php->capacity = php->size = 0;
}

插入

堆的插入是将数据插入到数组的尾部,然后再进行调整,使它满足堆的特性(大堆或小堆)

//堆的插⼊
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* temp=(HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);if (temp == NULL){perror("realloc fail!\n");exit(1);}php->arr = temp;php->capacity = newcapacity;}php->arr[php->size] = x;AdjustUp(php->arr, php->size);php->size++;
}

所以,堆的插入就分为两步:先插入,再调整 

删除

堆的删除是删除堆顶的数据,将堆顶的数据和最后一个结点的数据交换,这时堆顶数据就到了数组的尾部,直接删除数组的最后一个数据就行,删完了以后,就需要将现在的二叉树调整为堆结构

// 判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//堆的删除
void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));Swap(&php->arr[0], &php->arr[php->size-1]);php->size--;AdjustDown(php->arr, php->size, 0);
}

 

取堆顶元素和堆的数据个数

// 取堆顶的数据
HPDataType HeapTop(Heap* php)
{assert(php);assert(!HeapEmpty(php));return php->arr[0];
}// 堆的数据个数
int HeapSize(Heap* php)
{assert(php);return php->size;
}

堆的应用

堆排序

堆排序是借助堆的算法思想,而不是直接使用堆的数据结构来实现

堆排序的时间复杂度为:O(nlogn)

堆排序的实现思想:

1、先将传入的数组建成堆(升序建大堆,降序建小堆);

2、交换堆顶元素和堆尾元素;

3、对数组进行向下调整,使其保持堆的特性;

4、重复2和3的步骤,直到要调整的元素为1时结束,排序完成

在这里演示一个堆排序实现降序

这里的end一开始就为最后一个元素的下标,也是要调整元素个数,每次调整后要减减,也就是往前移

向下调整算法需要调整的就是元素的个数,所以是先调整,再end--

 代码为

#include"HeapSort.h"void HeapSortUp(int* arr,int n)//向上调整算法建堆:时间复杂度O(nlogn)
{//排升序建大堆//排降序建小堆//先建堆for (int i = 0; i < n; ++i)//这里建的堆是大堆{AdJustUp(arr, i);}//再排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);//交换堆顶和尾结点AdJustDown(arr, 0, end);end--;}}
void HeapSortDown(int* arr, int n)//向下调整算法建堆:时间复杂度O(n)
{//排升序建大堆//排降序建小堆//先建堆for (int i = (n - 1 - 1)/2; i >=0; i--){AdJustDown(arr, i, n);}//再排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);//交换堆顶和尾结点AdJustDown(arr, 0, end);end--;}}void test()
{int arr[] = { 6,3,11,9,16,17 };int n = sizeof(arr) / sizeof(arr[0]);//HeapSortUp(arr, n);HeapSortDown(arr, n);for (int i = 0; i < n; ++i){printf("%d ", arr[i]);}}int main()
{test();return 0;
}

在我写的堆排序有两种建堆方法,那哪一种建堆更加高效呢?

来让我们探究它们的复杂度

向上调整算法建堆

由该推算可得向上调整算法建堆的时间复杂度为O(nlogn)

根据图所示可知:

随着结点个数的逐渐增多,结点向上调整的次数也逐渐增多

向下调整算法建堆

由该推算可得向下调整算法建堆的时间复杂度为O(n)

根据图所示可知:

随着结点个数的逐渐增多,结点向下调整的次数也逐渐减少

ss所以在堆排序中最好使用向下调整算法建堆!!!

TOP-K问题

TOP-K问题是指在一堆数据中求前K个最大元素或最小元素,而一般情况下都是在数据量很大的情况下求解的一类问题

题目类型由:专业前10名、世界前500强、游戏中100的活跃玩家等

对于这类型的问题,能想到最简单的解法就是排序,但是在数据量很大的情况下,排序就不能实现不了,因为数据可能无法同时都存储在内存中

最佳的解决方法就是使用堆来解决

思路就是:

1、取N个数据的前K个元素,建堆(求前K个最大元素,建小堆;求前K个最小值,建大堆) 

2、用剩余N-K个元素依次和堆顶元素进行比较,

求前K个最大元素:如果大于堆顶元素就和堆顶元素交换(也就是入堆);

求前K个最小元素:如果大于堆顶元素就和堆顶元素交换(也就是入堆),

然后再将这K个元素进行调整使它们保持为堆

当N-K个元素比完了,堆中剩余的K个元素就是所求的前K个最大元素或最大元素

代码为:

#define _CRT_SECURE_NO_WARNINGS 1
#include"HeapSort.h"void CreateNDate()
{// 造数据int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void TopK()
{int k = 0;printf("请输入K:");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");exit(1);}//找最小的前K个数,建大堆int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("malloc fail!");exit(2);}//读取文件中前K个数据建堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdJustDown(minHeap, i, k);}//遍历剩下的n-k个数据,跟堆顶比较,谁小谁入堆//调整堆int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x < minHeap[0]){minHeap[0] = x;AdJustDown(minHeap, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}fclose(fout);fout = NULL;
}int main()
{TopK();//CreateNDate();return 0;
}

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

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

相关文章

oracle的静态注册和动态注册

oracle的静态注册和动态注册 静态注册&#xff1a; 静态注册 : 指将实例的相关信息手动告知 listener 侦 听 器 &#xff0c; 可以使用netmgr,netca,oem 以及直接 vi listener.ora 文件来实现静态注册&#xff0c;在动态注册不稳定时使用&#xff0c;特点是&#xff1a;稳定&…

postgresql按照年月日统计历史数据

1.按照日 SELECT a.time,COALESCE(b.counts,0) as counts from ( SELECT to_char ( b, YYYY-MM-DD ) AS time FROM generate_series ( to_timestamp ( 2024-06-01, YYYY-MM-DD hh24:mi:ss ), to_timestamp ( 2024-06-30, YYYY-MM-DD hh24:mi:ss ), 1 days ) AS b GROUP BY tim…

调试器 gdb/cgdb 的使用

一. touch mycode.c vim mycode.c cgdb 下载 Ubuntu&#xff1a;sudo apt-get install -y cgdb Centos: sudo yum install -y cgdb Linux 下我们编译好的代码无法直接调试 g/gcc 默认的工作模式是release模式 程序要调试&#xff0c;必须是debug模式&#xff0c;编译时…

通过DataWorks实现MaxCompute跨项目迁移

本文为您介绍如何配置不同MaxCompute项目并实现数据迁移。 背景信息 本文使用的被迁移的原始项目为教程《简单用户画像分析&#xff08;MaxCompute版&#xff09;》中的WorkShop2023项目&#xff0c;您需要再创建一个迁移目标项目&#xff0c;用于存放原始项目的表、资源、配置…

【Linux】安装cuda

一、安装nvidia驱动 # 添加nvidia驱动ppa库 sudo add-apt-repository ppa:graphics-drivers/ppa sudo apt update# 查找推荐版本 sudo ubuntu-drivers devices# 安装推荐版本 sudo apt install nvidia-driver-560# 检验nvidia驱动是否安装 nvidia-smi 二、安装cudatoolkit&…

Vue.js 学习总结(14)—— Vue3 为什么推荐使用 ref 而不是 reactive

前言 ref 和 reactive 是 Vue3 中实现响应式数据的核心 API。ref 用于包装基本数据类型&#xff0c;而 reactive 用于处理对象和数组。尽管 reactive 似乎更适合处理对象&#xff0c;但 Vue3 官方文档更推荐使用 ref。 我的想法&#xff0c;ref就是比reactive好用&#xff0c;…

ctfshow-Misc入门(1-16)

misc1 查看图片得到flag misc2 1、打开文本&#xff0c;发现以“塒NG”开头 3、修改文件格式为png格式 4、查看图片&#xff0c;得到flag *遇到的问题&#xff1a;无法直接修改后缀名 *解决方法&#xff1a;需要点击文件夹&#xff0c;然后点击查看&#xff0c;将文件拓…

自动驾驶概念

1.线控底盘 由五大系统构成&#xff1a;线控转向、线控制动系统、线控换挡、线控油门踏板以及线控悬架。 2.自动驾驶分级 L1级别&#xff0c;也被称作驾驶支援阶段。在这一阶段&#xff0c;车辆系统能够根据驾驶环境来辅助驾驶者进行方向盘操作或减速操作中的一项&#xff0c…

【C】错误的变量定义导致sprintf()‌输出错误

问题描述 刚刚写一个用AT指令透传相关的函数&#xff0c;需要用到sprintf()‌拼接字符串。 结果发现sprintf()‌拼接出来的内容是错误的&#xff0c;简化后的代码如下&#xff1a; const char AT_CIPSEND_FIX_LENGTH_HEADER[11] "ATCIPSEND"; // 错误的&#xff0…

【Pytest+Yaml+Allure】实现接口自动化测试框架

一、框架思想 requestsyamlpytestallure实现接口自动化框架。结合数据驱动和分层思想&#xff0c;将代码与数据分离&#xff0c;易维护&#xff0c;易上手。使用yaml编写编写测试用例&#xff0c;利用requests库发送请求&#xff0c;使用pytest管理用例&#xff0c;allure生成…

内网渗透横向移动1

1.信息收集 &#xff08;1&#xff09;判断域控 shell net time /domain shell ping OWA2010CN-God.god.org &#xff08;2&#xff09;主机探测 浏览探测->网络探测 主机列表显示&#xff1a; &#xff08;3&#xff09;域用户收集&#xff1a; shell net user /domain…

C++初阶——类和对象(下)

目录 1、再探构造函数——初始化列表 2、类型转换 3、static成员 4、友元 5、内部类 6、匿名对象 7、对象拷贝时编译器的优化(了解) 1、再探构造函数——初始化列表 1. 构造函数初始化除了使用函数体内赋值&#xff0c;还有一种方式——初始化列表&#xff0c; 初始化列…

数据指标与标签在数据分析中的关系与应用

导读&#xff1a;分享数据指标体系的文章很多&#xff0c;但讲数据标签的文章很少。实际上&#xff0c;标签和指标一样&#xff0c;是数据分析的左膀右臂&#xff0c;两者同样重要。实际上&#xff0c;很多人分析不深入&#xff0c;就是因为缺少对标签的应用。今天系统的讲解下…

Exploring Prompt Engineering: A Systematic Review with SWOT Analysis

文章目录 题目摘要简介方法论背景相关工作评估结论 题目 探索快速工程&#xff1a;基于 SWOT 分析的系统评价 论文地址&#xff1a; https://arxiv.org/abs/2410.12843 摘要 在本文中&#xff0c;我们对大型语言模型 (LLM) 领域的提示工程技术进行了全面的 SWOT 分析。我们强…

Android 常用命令和工具解析之内存相关

目录 1 基本概念 1.1 PSS & RSS & USS & VSS 1.1.1 PSS 1.1.2 RSS 1.2 Dirty & Clean & SwapPss 1.2.1 Private Dirty 1.2.2 Private Clean 1.2.3 SwapPss Dirty 1.3 Swap & buffers & cache 1.3.1 Swap 1.3.2 buffers 1.3.3 cache 2…

使用Go 语言连接并操作 MySQL 数据库

新建项目&#xff0c;我这里使用的vscode&#xff1a; 1.新建项目初始化&#xff1a; 手动创建工程文件夹go安装目录->src->projectName 在项目下创建 main.go文件&#xff1a; 在vscode中点击文件->打开文件夹&#xff0c;选择刚刚新建的文件夹。打开后&#xff0…

YOLOv11融合[NeurlS2022]递归门控卷积gnconv模块及相关改进思路

YOLOv11v10v8使用教程&#xff1a; YOLOv11入门到入土使用教程 YOLOv11改进汇总贴&#xff1a;YOLOv11及自研模型更新汇总 《HorNet: Efficient High-Order Spatial Interactions with Recursive Gated Convolutions》 一、 模块介绍 论文链接&#xff1a;https://arxiv.org…

从零开始-VitePress 构建个人博客上传GitHub自动构建访问

从零开始-VitePress 构建个人博客上传GitHub自动构建访问 序言 VitePress 官网&#xff1a;VitePress 中文版 1. 什么是 VitePress VitePress 是一个静态站点生成器 (SSG)&#xff0c;专为构建快速、以内容为中心的站点而设计。简而言之&#xff0c;VitePress 获取用 Markdown…

使用Notepad++工具去除重复行

使用Notepad工具去除重复行 参考链接&#xff1a;https://blog.csdn.net/londa/article/details/108981396 一 、使用正则表达式 1、对文本进行排序&#xff0c;让重复行排在一起 2、使用正则表达式替换&#xff08;注意&#xff09;^(.*?)$\s?^(?.*^\1$) 在替换时选择正…

RabbitMQ和RocketMQ相关面试题

RabbitMQ和RocketMQ面试题 RabbitMQ1.RabbitMQ各部分角色2.如何确保RabbitMQ消息的可靠性&#xff1f;3.什么样的消息会成为死信&#xff1f;4.死信交换机的使用场景是什么&#xff1f;5.TTL6.延迟队列7.消息堆积问题8.MQ集群 RocketMQ1.RocketMQ各部分角色2.RocketMQ如何保证高…