请将已备案网站接入访问,门户网站建设流程,中国企业500强企业名单,网站域名提交作者主页 #x1f4da;lovewold少个r博客主页 ➡️栈和队列博客传送门 #x1f333;参天大树充满生命力#xff0c;其根深叶茂#xff0c;分枝扶疏#xff0c;为我们展示了数据分治的生动形态 目录
#x1f333; 树
树的常见概念
#x1f4d2;树的表示
二叉树
一… 作者主页 lovewold少个r博客主页 ➡️栈和队列博客传送门 参天大树充满生命力其根深叶茂分枝扶疏为我们展示了数据分治的生动形态 目录 树
树的常见概念
树的表示
二叉树
一棵二叉树是结点的一个有限集合该集合:
二叉树的基本类型
满二叉树完美二叉树
完全二叉树 二叉树的性质
二叉树的存储方式
顺序存储
链式存储
堆 堆的定义
堆的常用操作
堆的初始化
堆的构建
堆的向上调整的堆化算法
堆的向下调整的堆化算法
编辑
时间复杂化分析
堆的插入
堆的删除
获取堆顶元素
获取堆有效元素个数
堆的判空
堆的销毁
完整代码
堆的应用
️Top-K问题
堆实现逻辑
️堆排序
✒️总结 前言 树木随处可见对于树的形容我们总是以枝繁叶茂树木丛生等来形容它。一颗树的主干能长出许多的分支每一颗分支上又可以有更多分支。而这和我们要学的新结构抽象成的逻辑结构极为相似。 前面我们学习的数据结构大多数都是一对一的关系前面接触的单链表栈等无外乎是对于数据的存储和查找。可是现实中还存在着一对多的关系也就需要研究这种一对多的数据关系——树Tree。同时树中有特殊的完全二叉树还有特殊的完全二叉树——堆。 树
树是一种非线性的数据结构代表这祖先和后代之间的派生关系树是一种由nn0个节点组成的集合其中:
有且仅有一个节点被指定为根节点其余节点被分为mm0个互不相交的子集每个子集本身也是一棵树称为根的子树。
树在我们的计算机中主要应用为文件的管理这里我们来用Linux更加直观的展示树在文件管理中的应用。 我们进入Linux系统的根目录这就好比是文件管理的的主干。 在这个根目录下我们还可以看见许多的文件以及文件夹而我们知道的是文件夹中还可以套文件夹和文件 我们利用tree指令就可以看见整个树形结构的文件系统观察tmp我们就能看见文件就像一颗树一样分支纵横枝繁叶茂而tmp也只为根的一个分支。 比如在根目录的树形展示中通过记数我们发现拥有17008个文件夹和115225个文件。而文件却多而不乱通过访问各个分支就能访问到想要的文件这就是树的魅力所在。 树的常见概念
【根节点 root】位于二叉树顶层的节点没有父节点。【叶子节点 leaf】没有子节点的节点左右节点指向都为空。【非终端节点或分支节点】度不为0的节点。【双亲节点或父节点】若一个节点含有子节点则称这个节点为子节点的父节点。【孩子节点或子节点】一个节点含有的子树的根节点为该节点的子节点。【兄弟节点】具有相同父节点的节点称为兄弟节点。【堂兄弟节点】双亲在同一层的节点互为堂兄弟节点。【节点的祖先】从根节点到该节点经过的所有分支节点可称之为该节点的祖先。【边 edge】连接两个节点的线段即可以抽象为指针。【节点的度】一个节点含有的子树的个数称为该节点的度。二叉树的度叶子节点为零取值为012。【树的度】一棵树最大的节点的度即为树的度。【节点的层次 level】从顶至底部递增根节点所在层为1。【节点高度 height】高度通常表述为根节点到叶子节点的层距离。【二叉树高度 height】根节点到叶子节点的层距离。【深度 depth】到根节点经过的层数。【森林 Forest】多棵互不相交的树的集合。对每个节点而言其子树的集合即为森林。但是一般不这么去理解针对与后面的递归逻辑我们只简单抽象为左右子树即可。
树的表示 树结构相对与以前的数据结构要更加复杂既要保存节点的值域也要保存节点和节点之间的关系。树在实际中有多种表示方式如双亲表示法孩子表示法孩子双亲表示法以及孩子兄弟表示法。这里我们简单的用孩子兄弟表示法。即我们预想并不能考虑到树的根节点到底有多少分支但是我们可以不去考虑根节点去链接所有孩子节点。我们通过根管老大老大管老二的链接方式让父节点链接左孩子让左孩子去链接他的兄弟节点。 逻辑上这一棵树的概念如图所示在代码上我们通过孩子兄弟表示法进行连接。
typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};二叉树 二叉树是一种特殊的树在日常操作和解决问题的过程中我们更常使用二叉树。什么是二叉树呢顾名思义即每一颗节点有两个分支。“一分二支”即作为二叉树操作中主要思想。与链表类似二叉树的基本单元为节点每一个节点包含值左节点右节点。每一个根节点都通过指针分别指向他的左右节点在二叉树中除叶子节点外其他所有节点都包含子节点和非空子树。 一棵二叉树是结点的一个有限集合该集合: 或者为空 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 从上图可以看出 二叉树不存在度大于2的结点 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 二叉树的基本类型
满二叉树完美二叉树
满二叉树所有层的节点都被完全填满的二叉树。
在满二叉树中叶节点的度为零其余所有节点的度为2若树的高度为h则节点总数为计算方式即为等比数列的前h项合呈现标准的指数关系。 完全二叉树
完美二叉树的除了最底层未被填满其余层都被填满且叶子节点是从左往右的填充。 二叉树的性质 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有 2^(i-1) 个结点。若规定根节点的层数为1则深度为h的二叉树的最大结点数是 2^h-1。对任何一棵二叉树, 如果度为0其叶结点个数为 n0度为2的分支结点个数为 n2则有 n0n21。若规定根节点的层数为1具有n个结点的满二叉树的深度h log_2(n1)。 (ps log_2 是以2为底n1为对数)对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 若i0i位置节点的双亲序号(i-1)/2若i0i为根节点编号无双亲节点若2i1n左孩子序号2i1否则无左孩子若2i2n右孩子序号2i2否则无右孩子 二叉树的存储方式 关于数据结构的存储方式我们一般使用两种方式即顺序存储和链式存储二叉树我们同样使用这两种方式。这时候不免要考虑了链式存储能理解顺序存储又怎么能实现这个逻辑呢。首先需要清楚的是顺序存储即数组更适合连续存储这就比较适合对完全二叉树的存储。
顺序存储 我们通过对一颗完美二叉树建立节点索引按照层序遍历的方式进行存储就会发现孩子节点和双亲节点可以通过映射公式建立逻辑联系。 即通过任意一个孩子节点的索引值可以通过 (n-1)/2向下去整找到其唯一的双亲节点索引。通过一个双亲节点的索引值 2*n1 可以找到唯一的左孩子节点索引再通过左孩子节点1即可访问右孩子节点。 非完全二叉树由于后续节点之间不联系存在空的情况因此不太适合用数组去存储。数组对于完全二叉树的最优体现就是对堆的实现。 链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是 链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链后面到高阶数据结构如红黑树等会用到三叉链因此不做过多铺垫。
堆 不是完全二叉树的篇章么怎么又跳到了堆。别急堆是基于完全二叉树的升华体现要了解树不妨先看看堆。 堆的定义
堆是一种特殊的完全二叉树它可以用数组来实现数组中的每个元素对应一个结点。
堆有两种类型大堆和小堆。 大堆中每个结点的值都大于等于它的两个子结点的值小堆中每个结点的值都小于等于它的两个子结点的值。堆中根结点的值是堆中最大或最小的值可以用来实现优先队列或堆排序等算法。堆中某个结点的编号为i那么它的父结点的编号为(i-1)/2它的左子结点的编号为2i1它的右子结点的编号为2i2。堆中某个结点所在的层数为logi1向上取整其中log在我们程序界是以2为底的对数。例如编号为7的结点所在的层数为log83。 堆的存储上并不是有序的但在在每一棵子树都存在根节点相对于左右子树为最大值大堆最小值小堆。
堆的常用操作 //堆的初始化
void HeapInit(Heap* hp);
// 堆的构建
void HeapCreate(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);
// 堆的判空
int HeapEmpty(Heap* hp); 堆的初始化 堆由于用数组来进行存储父子节点采用索引进行定位。 typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap; void HeapInit(Heap* hp)
{assert(hp);hp-a NULL;hp-capacity hp-size 0;
} 通过任意一个孩子节点的索引值可以通过 (n-1)/2向下去整找到其唯一的双亲节点索引。通过一个双亲节点的索引值 2*n1 可以找到唯一的左孩子节点索引再通过左孩子节点1即可访问右孩子节点。 堆的构建 堆的构建简单来讲就是插入数据进堆由于插入的val并不能保证大小堆的根节点和左右子节点大小关系因此需要修复从插入节点到根节点路径上的每一节点。这个进行堆调节的一个过程也叫堆化。一般来讲建堆操作通常是对一个已经存在的数组进行堆化通过建堆利用堆的大小堆根节点的最大和最小进行排序等操作。因此在入堆过程中我们通常有两种堆化方式那么这两种方式的思维逻辑和时间复杂度怎么样呢
堆的向上调整的堆化算法 · 在建堆的过程中首先创建一个空堆然后遍历列表对每个元素依次入堆操作这种方式就是在构建堆的时候新元素进入堆末再通过对其祖先路径上元素进行比较如果子节点元素小于父节点则交换构建大堆相反,进行从底到顶的堆化. void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int child (parent) * 2 1;//索引找孩子节点while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent])//子节点小于父节点则交换{Swap(a[child], a[parent]);//用于交换自定义函数parent child;child child * 2 1;}else{break;}}
} 堆分为大堆小堆这里就用小堆代码来展示。 堆的向下调整的堆化算法 由上至下的调整操作方式和由下至上的操作相反构建堆的时候我们先将列表按照层序遍历的方式连接起来即可。后续我们需要调节根节点的值与其两个子节点的值进行比较根据大堆小堆的根节点与子节点来确定二者比较关系。然后循环执行此操作知道越过叶子节点或遇到无需交换的节点时结束。这里主要的思考方式就是找父比子。 要理解的是构建堆需要倒序遍历堆依次对每一个非叶子节点都需要执行向下调整的堆化。 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 (parent - 1) / 2;}else{break;}}
} 这里是以图示的大堆向下调整算法代码 时间复杂化分析 在构建堆的过程中通过这两种不同的算法我们有不同的建堆方式。
向上调整建堆 首先创建空堆遍历待插入的列表依次将每一个元素入堆即先将元素添加到堆末然后对该元素向上调整。元素数量为n每个元素入堆的时间复杂度为logn因此建堆整体时间在nlogn。这种建堆方式是上层先达到大小堆关系因此是从上至下的创建的堆。 向下调整建堆 和向上不同的是先将所有元素原封不动入堆然后按照倒序层次遍历堆依次对每一个非叶子节点进行向下调整当调整到叶子节点的时候调整完毕。这种建堆方式是下层先有序然后依次向上遍历建堆因此是从下至上创建的堆。 这里理解起来有点麻烦为什么向下调整是倒序建立的堆呢。答案其实很简单要对一个根节点进行如图所示的调整得先保证左右子树是一定的大小堆然后才能向下调整否则调整是没有意义的。而要保证每一个根节点的左右子树是堆只需要从倒数第二层即叶节点上一层开始向下调整保证左右子树和根节点的大小关系。往上遍历的过程中自然一直能保证左右子树是大堆或者小堆。 这种方式的时间复杂度是多少呢假设完全二叉树的节点数量为n则节点数量为(n1)/2(向下整除)因此需要堆化的数量为(n-1)/2。从顶至底部堆化的过程中每个节点最多堆化到叶子节点因此最大高度为二叉树高度logn所有时间复杂度为nlogn么
我们来点更加精确的计算。 一个节点从底到上的一个堆化中最大需要去调整的次数为该节点到叶子节点的距离而该距离为节点高度因此我们可以得到公式 节点数量*节点高度。 叶子节点不用去调整因此只需要计算到高度1即可。 Tn 2⁰ · h 2¹ · (h - 1) 2² · (h - 2) ...... 2ʰ⁻² · 2 2ʰ⁻¹ · 1 2ʰ · 0 把首尾两个元素简化记为①式 ①: Tn h 2¹ · (h - 1) 2² · (h - 2) ...... 2ʰ⁻² · 2 2ʰ⁻¹ 对①等于号左右两边乘以2记为②式 ②: 2Tn 2¹ · h 2² · (h - 1) 2³ · (h - 2) ...... 2ʰ⁻¹ · 2 2ʰ 那么用②式减去①式其中②式的操作数右移一位使指数相同的部分对齐错位相减法。 得到 Tn n - log₂(n 1)约等于n 即向下调整的时间复杂度仅O(n),非常高效因此这里我们建堆过程中采用向下调整的方法。
void HeapCreate(Heap* hp, HPDataType* a, int n)//对已有数组可以直接构建堆
{assert(hp);assert(a);hp-a (HPDataType*)malloc(sizeof(HPDataType) * n);//开辟空间如果已有数组之间开辟等大空间if (hp-a NULL){perror(malloc fail);exit(-1);}hp-capacity n;hp-size n;memcpy(hp-a, a, sizeof(HPDataType) * n);for (int i 0; i n; i){AdjustUp(hp-a, i);}
}
堆的插入 堆插入新元素即先入堆末在对此进行向上调整即可。 void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp-size hp-capacity){int newcapacity hp-capacity0 ? 4 : hp-capacity * 2;HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}hp-a tmp;hp-capacity newcapacity;}hp-a[hp-size] x;hp-size;AdjustUp(hp-a, hp-size - 1);
} 堆的删除 删除元素我们要考虑的是怎么去删除比较有意义不论是大堆小堆我们能直接获取就是堆顶元素而且堆的性质能保证这个元素为堆最大或者最小。因此很显然直接删堆首元素嘛。但是当我们删除堆顶元素后怎么样能保证他继续是一个堆呢。 这个时候我们先将堆首和堆末替换扶小弟上位后面对小弟进行向下调整即可。 void HeapPop(Heap* hp)
{assert(hp);assert(hp-size 0);Swap(hp-a[0], hp-a[hp-size - 1]);hp-size--;AdjustDown(hp-a, hp-size, 0);
} 获取堆顶元素
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(hp-size 0);return hp-a[0];
}
获取堆有效元素个数
int HeapSize(Heap* hp)
{assert(hp);return hp-size;
}
堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);return hp-size 0;
}
堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp-a);hp-a NULL;hp-capacity hp-size 0;
}
完整代码
//头文件Heap.h
#pragma once
#includestdlib.h
#includestdbool.h
#includestdio.h
#includeassert.h
#includemalloc.h
#includestring.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;//自上而下调整
void AdjustUp(HPDataType* a, int child);
//自下而上调整
void AdjustDown(HPDataType* a, int n, int parent);
//堆的初始化
void HeapInit(Heap* hp);
// 堆的构建
void HeapCreate(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);
// 堆的判空
int HeapEmpty(Heap* hp);
//交换
void Swap(HPDataType* a, HPDataType* b);
//打印
void HeapPrint(Heap* hp);//实现源文件 Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeHeap.hvoid HeapInit(Heap* hp)
{assert(hp);hp-a NULL;hp-capacity hp-size 0;
}
void HeapCreate(Heap* hp, HPDataType* a, int n)//对已有数组可以直接构建堆
{assert(hp);assert(a);hp-a (HPDataType*)malloc(sizeof(HPDataType) * n);//开辟空间如果已有数组之间开辟等大空间if (hp-a NULL){perror(malloc fail);exit(-1);}hp-capacity n;hp-size n;memcpy(hp-a, a, sizeof(HPDataType) * n);for (int i 0; i n; i){AdjustUp(hp-a, i);}
}
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp *a;*a *b;*b tmp;
}
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 (parent - 1) / 2;}else{break;}}
}
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int child (parent) * 2 1;//索引找孩子节点while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent])//子节点小于父节点则交换{Swap(a[child], a[parent]);//用于交换自定义函数parent child;child child * 2 1;}else{break;}}
}
void HeapDestory(Heap* hp)
{assert(hp);free(hp-a);hp-a NULL;hp-capacity hp-size 0;
}
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp-size hp-capacity){int newcapacity hp-capacity0 ? 4 : hp-capacity * 2;HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}hp-a tmp;hp-capacity newcapacity;}hp-a[hp-size] x;hp-size;AdjustUp(hp-a, hp-size - 1);
}
void HeapPop(Heap* hp)
{assert(hp);assert(hp-size 0);Swap(hp-a[0], hp-a[hp-size - 1]);hp-size--;AdjustDown(hp-a, hp-size, 0);
}
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(hp-size 0);return hp-a[0];
}
int HeapSize(Heap* hp)
{assert(hp);return hp-size;
}
int HeapEmpty(Heap* hp)
{assert(hp);return hp-size 0;
}void HeapPrint(Heap* hp)
{assert(hp);for (size_t i 0; i hp-size; i){printf(%d , hp-a[i]);}printf(\n);
}
堆的应用
️Top-K问题 在日常生活中我们能看见各种各样的榜单或者是你微信运动的步数亦或者是美团的餐馆评分前五名又或者是自己游戏中的排行榜。很多情况下这些排行榜并不会展示所有的数据这样的数据反而没有任何参考意义。很多情况下我们总是盯这Top-100,Top-10。因为这些根据某种评分后决定的数据更有含金量是大多数人的选择或者想知道的信息。 在实现中其实就可以利用堆完成这样子的Top-K问题。
堆实现逻辑
首先建立一个小堆其堆顶元素最小。再将数组的前K个元素入堆。从第K1个元素开始若当前元素大于堆顶元素堆顶元素出堆。当前元素入堆并调整。遍历整个数组后堆中保存的就是最大k个元素。 整个建堆的过程时间复杂度就很低相比于多次排序找最值时间复杂度在k值最小时间复杂度O(n)k较大时,时间复杂度也不会超过O(nlogn)。这种方式在开辟空间也只用开辟K个节点的空间空间复杂度也很低。 这种方式适用于动态的数据流变换在不断加入数据时堆内元素始终只需要维护其K个时刻可以保证K个元素及时更新。 这里我们通过文件操作进行写入随机值并且利用这些随机值解决Top-K问题来演示。
void PrintTopK(const char* filename, int k)
{// 1. 建堆--用a中前k个元素建堆FILE* fout fopen(filename, r);if (fout NULL){perror(fopen fail);return;}int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(malloc fail);return;}for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);}// 前k个数建小堆for (int i (k - 2) / 2; i 0; --i){AdjustDown(minheap, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换不满则则替换int x 0;while (fscanf(fout, %d, x) ! EOF){if (x minheap[0]){// 替换你进堆minheap[0] x;AdjustDown(minheap, k, 0);}}for (int i 0; i k; i){printf(%d , minheap[i]);}printf(\n);free(minheap);fclose(fout);
}// fprintf fscanfvoid CreateNDate()
{// 造数据int n 10000000;//造了一个千万级别的数据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) % 10000000;//随机值fprintf(fin, %d\n, x);//写入文件}fclose(fin);//关闭文件
}int main()
{CreateNDate();PrintTopK(data.txt, 100);//Top-100return 0;
} 可以看见这个数据量还是相当大的要是用排序等去实现得跑到天昏地暗。我们改变了数据的几个值观察他能否找出来可以看见8133211323这个数据能很快被找出来。 ️堆排序 堆排序一个指定的数列首先我们要确定的是排升序还是降序。升序构建大堆降序构建小堆。 但是我们还要思考的是对于一个已有的数列堆是需要额外开辟一块空间进行打印操作么。很显然我们需要将一个数组转变为一个有序数组我们可以直接用这个数组本身作为一个堆然后对数组依次入堆并向下调整。升降序只需要大小堆构建控制即可。
void HeapSort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
} ✒️总结 堆Heap是二叉树和数组的一种抽象数据结构 堆的基本概念 堆是一种树状数据结构通常是一个完全二叉树。堆分为两种主要类型最大堆Max Heap和最小堆Min Heap具体取决于根节点的值与其子节点的关系。在最大堆中父节点的值大于或等于子节点的值最大值位于根节点。在最小堆中父节点的值小于或等于子节点的值最小值位于根节点。 堆常用的应用 堆排序堆排序是一种高效的排序算法通过使用堆数据结构可以将数组以O(n log n)的时间复杂度进行原地排序。堆可以用于Top-K算法问题。 堆的难点和理解难点 堆的插入和删除操作需要维护堆的性质这涉及到向下调整和向上调整操作。确保堆的性质在插入或删除元素后仍然得到维护需要深刻理解堆的特性。堆排序算法的实现相对复杂需要理解堆的建立和维护。在实际应用中选择最大堆还是最小堆取决于问题的性质。 作者个人水平有限文章难免出错如有错误欢迎指正
