我国旅游网站的建设,湖南正规关键词优化,如何制作地图动画,seo推广教程视频目录
一.树与二叉树
1.树的概念与相关术语#xff1a;
2.二叉树#xff1a;
#xff08;1#xff09;定义#xff1a;
#xff08;2#xff09;特殊的二叉树#xff1a;
#xff08;3#xff09;完全二叉树
#xff08;4#xff09;二叉树的存储结构#x…目录
一.树与二叉树
1.树的概念与相关术语
2.二叉树
1定义
2特殊的二叉树
3完全二叉树
4二叉树的存储结构
二.堆的概念与性质
1.堆的概念
2.堆的重要性质
三.堆的具体代码实现
1.堆的结构
2.堆的初始化与销毁
3.向上调整算法和向下调整算法
1向上调整算法
2向下调整算法
3总结两种算法的区别
4堆元素的插入
5堆元素的删除
6取堆顶元素
7堆的判空
四.堆的具体应用
1.基于已有堆结构的堆排序通过不断取堆顶
2.数组建堆先向下调整建堆再向上调整 一.树与二叉树
1.树的概念与相关术语 概念 树是⼀种非线性的数据结构它是由 nn0 个有限结点组成⼀个具有层次关系的集合。把它叫做 树是因为它看起来像⼀棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根结点没有前驱结点。 除根结点外其余结点被分成 M(M0) 个互不相交的集合 T1、T2、……、Tm 其中每⼀个集合 Ti( 又是⼀棵结构与树类似的子树。每棵⼦树的根结点有且只有⼀个前驱可以 有 0 个或多个后继。因此树是递归定义的 相关术语 父结点/双亲结点若⼀个结点含有子结点则这个结点称为其子结点的父结点 子结点/孩子结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点 结点的度⼀个结点有⼏个孩⼦他的度就是多少 树的度⼀棵树中最⼤的结点的度称为树的度 叶子结点/终端结点度为 0 的结点称为叶结点 分支结点/非终端结点度不为 0 的结点 兄弟结点具有相同父结点的结点互称为兄弟结点(亲兄弟) 结点的层次从根开始定义起根为第 1 层根的⼦结点为第 2 层以此类推 树的高度或深度树中结点的最大层次 路径⼀条从树中任意节点出发沿父节点-子节点连接达到任意节点的序列 2.二叉树
1定义 二叉树满足以下两个特点 1. 二叉树不存在度大于 2 的结点 2. 二叉树的子树有左右之分次序不能颠倒因此⼆叉树是有序树 2特殊的二叉树 满二叉树 ⼀个二叉树如果每⼀个层的结点数都达到最⼤值则这个二叉树就是满二叉树。也就是说如果⼀ 个二叉树的层数为 K 且结点总数是2的k次方-1 则它就是满二叉树。 3完全二叉树 完全二叉树是效率很高的数据结构完全二叉树是由满⼆叉树而引出来的。 对于深度为 K 的有 n 个 结点的⼆叉树当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 至 n 的结点⼀⼀对应时称 之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树 简单来说完全二叉树和满二叉树的区别·就在于那它们的区别主要在于结构上的差异满二叉树要求每一层都填满而完全二叉树只要求前几层填满最后一层可以填到最左边但不一定全部填满 4二叉树的存储结构
顺序存储即下面我要说的堆与链式结构
我在这篇文章主要说明的是二叉树的顺序存储链式结构的介绍我会详细再另外写一篇文章 二.堆的概念与性质
1.堆的概念 堆Heap是计算机科学中的一种特殊数据结构它可以被视为一棵完全二叉树的数组表示形式。堆的特点是节点的值总是不大于或不小于其父节点的值这种性质使得堆的根节点总是该数据结构中的最大值或最小值 其中堆的根节点是该数据结构中的最大值则称该堆为大根堆 堆的根节点是该数据结构中的最小值则称该堆为小根堆。 堆满足以下特性 *堆中某个结点的值总是不大于或不小于其父结点的值 *堆总是⼀棵完全二叉树 2.堆的重要性质 对于具有 n 个结点的完全⼆叉树如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号则对于序号为 i 的结点有 1. 若 i0 i 位置结点的双亲序号 (i-1)/2 i0 i 为根结点编号无双亲结点 2. 若 2i1左孩子序号 2i1 2i1n 否则无左孩子 3. 若 2i2右孩子序号 2i2 2i2n 否则无右孩子 三.堆的具体代码实现 1.堆的结构
//堆的结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//有效数据个数int capacity;//空间大小
}HP;
2.堆的初始化与销毁
//堆的初始化
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;
}
3.向上调整算法和向下调整算法
1向上调整算法 目标 将新插入的节点或被修改的子节点调整到合适位置使其满足堆性质 步骤 从当前节点开始比较其与父节点的值 如果违反堆性质如最小堆中子节点值更小则交换两者 重复上述过程直到到达根节点或满足堆性质 void AdjustUp(HP* hp, int child)//传入堆和调整的起始孩子
{int parent (child - 1) / 2;//公式while (child 0)//注意退出条件{//建小根堆if (hp-arr[parent] hp-arr[child]){swap(hp-arr[parent], hp-arr[child]);child parent;parent (child - 1) / 2;}else{break;//如果不用换了。说明这个堆正常了和adjustdown的退出原因一样}}
}
2向下调整算法 目标 将删除根节点后的最后一个元素调整到堆顶或修复被修改的根节点 步骤 找到当前节点的子节点左、右选出符合堆性质的子节点如最小堆中较小的子节点 如果当前节点违反堆性质如比子节点更大则与子节点交换 重复上述过程直到叶子节点或满足堆性质 void AdjustDown(HP* hp, int parent, int n)//n是向下调整的下界范围
{int child parent * 2 1;//公式while (child n){//建小根堆if (child 1 n hp-arr[child 1] hp-arr[child])//child1的目的是确保两个孩子结点都是有意义的结点{child;}if (hp-arr[parent] hp-arr[child]){swap(hp-arr[parent], hp-arr[child]);parent child;child parent * 2 1;}else{//我最小的孩子都比父节点大那么这个堆就是正常堆了直接退出break;}}
}3总结两种算法的区别 1. 方向不同 向上调整 从子节点向根节点方向调整 例如插入新节点时将其放在堆末尾然后逐层与父节点比较并交换 向下调整 从父节点向叶子节点方向调整 例如删除根节点后将末尾节点移到根位置逐层与子节点比较并交换 2. 应用场景不同 向上调整 插入新元素新元素被添加到堆的末尾可能破坏堆性质需向上调整 节点值增大在最大堆中若某节点的值变大可能需要向上调整 向下调整 删除根节点删除堆顶后将末尾节点移到堆顶需向下调整 节点值减小在最大堆中若某节点的值变小可能需要向下调整 构建堆从最后一个非叶子节点开始逐个向下调整时间复杂度为 O(n) 3. 操作步骤不同 向上调整 比较当前节点与父节点 若违反堆性质如最大堆中当前节点值更大则交换两者 重复直到到达根节点或满足堆性质 向下调整 比较当前节点与左右子节点 选择最大或最小的子节点根据堆类型 若子节点违反堆性质则交换两者 重复直到到达叶子节点或满足堆性质 4. 时间复杂度 常数因子差异向下调整需比较两个子节点操作略复杂向上调整仅需比较父节点 以下是时间复杂度的具体算法 4堆元素的插入
void HeapPush(HP* hp, int x)
{assert(hp);//判断空间是否已满if (hp-capacity hp-size){//注意capacity的单位是个不是字节int newcapacity hp-capacity 0 ? 4 : 2 * hp-capacity;//第一次开就开四个//空间开辟//注意这里是realoc不是malloc//所有链式结构的用malloc咱们开辟新节点//所有线性结构底层是数组的咱们就realoc//因为咱们要保留数组之前的数据所以必须要扩容而不是重新开辟HP* newspace (HP*)realloc(hp-arr, newcapacity * sizeof(int));if (newspace NULL){perror(malloc wrong!);exit(1);}hp-arr newspace;hp-capacity newcapacity;}//直接插入//size是当前有效元素个数对应的也是下一个该存放元素位置的下标hp-arr[hp-size] x;hp-size;//插入元素之后配套进行向上调整AdjustUp(hp, hp-size - 1);//注意传入的是下标
}5堆元素的删除
void HeapPop(HP* hp)
{//几乎所有的数据结构在插入元素是要断言这个数据结构是否存在//在删除元素的时候断言这个数据结构中要含有元素assert(!empty(hp));//删除根元素swap(hp-arr[0], hp-arr[hp-size - 1]);hp-size--;//配套使用向下调整算法AdjustDown(hp, 0, hp-size);
}
6取堆顶元素
int HeapTop(HP* hp)
{assert(!empty(hp));//empty里面判断了这个堆必须存在所以说不用再在这判断了、return hp-arr[0];
}
7堆的判空
bool empty(HP* hp)
{assert(hp);return hp-size 0;
} 四.堆的具体应用
1.基于已有堆结构的堆排序通过不断取堆顶
// 1、需要堆的数据结构
// 2、空间复杂度 O(N)
void HeapSort(int* a, int n)
{HP hp;for(int i 0; i n; i){HPPush(hp,a[i]);}int i 0;while (!HPEmpty(hp)){a[i] HPTop(hp);HPPop(hp);}HPDestroy(hp);
}2.数组建堆先向下调整建堆再向上调整
// 升序建⼤堆
// 降序建⼩堆
// O(N*logN)
void HeapSort(int* a, int n)
{// a数组直接建堆 O(N)for (int i (n-1-1)/2; i 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}欧克到这里就差不多把数组结构的堆介绍完了更多的就是堆的Top-K问题了感兴趣的可以先去了解我后续会写关于它的解析
那就这样吧
全文终
