自己做图片的网站链接,国内企业网站欣赏,做任务领黄钻的网站,网站架构设计图怎么做#x1f387;个人主页#xff1a;Ice_Sugar_7 #x1f387;所属专栏#xff1a;C启航 #x1f387;欢迎点赞收藏加关注哦#xff01; 文章目录 #x1f349;树#x1f349;二叉树#x1f34c;特殊二叉树#x1f34c;二叉树的性质#x1f34c;存储结构 #x1f349;… 个人主页Ice_Sugar_7 所属专栏C启航 欢迎点赞收藏加关注哦 文章目录 树二叉树特殊二叉树二叉树的性质存储结构 堆堆的结构插入向上调整算法时间复杂度分析 删除向下调整算法时间复杂度分析 堆的创建堆的初始化堆排序top k 问题 写在最后 树
●树是一种非线性的数据结构它是由nn0个结点组成具有层次关系 ●有一个特殊的结点称为根结点根节点没有前驱结点 ●除根节点外其余结点被分成M(M0)个互不相交的集合每个集合是一棵子树
二叉树
二叉树一个非空结点的子树为空或者至多两个子树左子树和右子树 从这个图可以看出 二叉树不存在度大于2的结点 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 特殊二叉树
满二叉树每一层结点数都达到最大值的二叉树。如果一棵满二叉树有k层那它结点总数就是2^k-1 完全二叉树最后一层抠掉几个结点的满二叉树就是一般的完全二叉树满二叉树是特殊的完全二叉树
二叉树的性质
二叉树的性质都在下图了
存储结构
二叉树一般使用两种结构存储顺序结构和链式结构 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储 二叉树顺序存储在物理结构上是一个数组在逻辑结构上是一颗二叉树 我们的代码是按照其物理结构写的而具体想实现的函数接口则是根据逻辑结构展开的往下看入堆、出堆、调整等函数之后你就能理解这句话了
本文讲二叉树的顺序存储结构——堆正文开始 堆
堆分为两种大堆和小堆。 大堆除了叶子结点外所有结点的孩子都比自己小 小堆除了叶子结点外所有结点的孩子都比自己大 根据堆的逻辑结构可知大堆是上面的结点位于较低层次的结点大小堆是上面的结点小 堆的结构
堆的物理结构就是顺序表所以代码基本和顺序表一模一样
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;插入
插入这一步很简单就直接往数组插入元素注意检查容量是否足够并且插入后记得让size加1 插入后要对这个元素进行调整采用向上调整
向上调整算法
假设要建一个小堆那就要拿它和它的双亲进行比较如果它比双亲小就和双亲交换位置。假设数组名为_a大小为size那插入的结点下标为size-1它的双亲在数组中的下标就是size-1-1/2 这里要用循环将插入的结点记为child当child为0时即它到了堆顶循环终止。如果中途经比较后发现不用换位置的话说明调整好了直接break跳出循环 代码如下
typedef int HPDataType;void Swap(HPDataType* hp1, HPDataType* hp2) {HPDataType tmp *hp1;*hp1 *hp2;*hp2 tmp;
}//小堆向上调整
void AdjustUp(Heap* hp,int child) {assert(hp);int parent (child - 1) / 2;while (child 0) {if (hp-_a[child] hp-_a[parent]) //孩子比双亲大退出循环break;else {Swap((hp-_a[child]),(hp-_a[parent])); //两结点交换child parent;parent (parent - 1) / 2;}}
}时间复杂度分析
因为堆是完全二叉树而满二叉树也是完全二叉树为了简化问题就用满二叉树来证明了时间复杂度本来看的就是近似值多几个节点不影响最终结果下面向下调整算法的时间复杂度也这样处理 假设有n个结点那就有logn1层那每次向下调整最多遍历logn1次总共有n个结点那么就遍历n*logn1次时间复杂度就是ON*logN 删除
不能直接将数组往前挪一位因为这样虽然在物理结构数组上没什么问题但是在逻辑结构完全二叉树上就有问题了会打乱结点间的关系比如原先的兄弟现在变为父子父子变兄弟 有一个比较巧妙的解决办法就是将根结点和尾结点数组最后一个元素交换位置然后将新的尾结点删掉这样就不会影响到结点间的关系了 删掉后要进行向下调整这就涉及到向下调整算法了
向下调整算法
现在有一个数组它有n个元素从逻辑结构上看成是完全二叉树我们从根结点开始通过向下调整算法可以把它调整为一个小堆 这种算法的前提是左右子树必须是一个堆才能调整
int array[] {27,15,19,18,28,34,65,49,25,37};调整过程如图 每次调整先比较该结点两个孩子的大小现在要调整为小堆就先找出较小的孩子然后这个孩子和双亲进行比较若孩子双亲就把它和双亲交换位置反之则说明调整完毕
调整的过程显然也要用循环。我们将双亲结点记为parent左孩子结点记为child因为左右孩子下标相差1没必要用leftchild和rightchild进行区分。那右孩子就是child 1不过由于右孩子可能不存在当child为叶子结点时可能会有这种情况所以我们得在循环里面判断一下 这里采用假设法就是我们先假设左孩子是较小的结点因为右孩子可能不存在不方便假设如果右孩子存在的话就拿左右孩子进行比较最后将child赋给较小者 假设法相比于if语句可以有效简化代码具体可以看我之前那篇判断相交链表的题解or看下面的代码也ok文章链接判断相交链表 那循环的终止条件呢显然当childn的时候就要跳出循环了 代码如下
void AdjustDown(HPDataType* a,int n,int parent) { //n为数组大小assert(a);int child 2 * parent 1; //左孩子下标while (child n) {if (child 1 n a[child1] a[child]) { //右结点存在并且右孩子比左孩子小child; //将child设为右孩子结点等会儿拿它和双亲进行比较决定是否交换}if (a[child] a[parent]) {Swap(a[child], a[parent]);parent child; //更新双亲结点child parent * 2 1; //更新孩子结点}elsebreak; //不用换位置说明调整完毕}
}时间复杂度分析 “向下移动”的层数指的是最多要调整几次即从这个结点开始一直调整到叶子结点为止最坏的情况 从结果可以看出向下调整的时间复杂度O(N)比向上调整的小所以建议使用向下调整 堆的创建堆的初始化
建堆既可以建一个空堆也可以根据一个现成的数组建堆 建空堆就是将数组赋为空指针然后size和capacity都赋为0。和顺序表初始化一样不多赘述 这里主要来讲数组建堆 思路是给堆开辟空间拷贝调整 ●开空间数组多大就开多大 ●拷贝使用memcpy将数组的元素拷贝给堆 ●调整向上调整or向下调整
先展示向上调整
void HeapCreate(Heap* hp, HPDataType* a, int n) {assert(hp);assert(a);HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType) * n);if (tmp NULL) {perror(malloc fail);exit(-1);}hp-_a tmp;hp-_capacity hp-_size n;memcpy(hp-_a, a, n * sizeof(HPDataType)); //把数组数据拷贝到堆的数组中int parent (hp-_size - 1) / 2;for (int i 1; i n; i) { // 调整建堆AdjustUp(hp, i);}
}也可以复用刚才写的入堆函数因为它自带向上调整函数。而且push函数是将数组的元素一个一个放进堆的这样就不需要memcpy了代码如下为方便观察我把向上调整函数和入堆函数也放在下面
//小堆向上调整
void AdjustUp(Heap* hp, int child) {assert(hp);int parent (child - 1) / 2;while (child 0) {if (hp-_a[child] hp-_a[parent]) //孩子比双亲大退出循环break;else {Swap(hp-_a[child], hp-_a[parent]); //两结点交换child parent;parent (child - 1) / 2;}}
}void HeapPush(Heap* hp, HPDataType x) {assert(hp);//如果满了 那就要扩容if (hp-_capacity hp-_size) {int newcapacity hp-_capacity 0 ? 4 : 2 * hp-_capacity;HPDataType* tmp (HPDataType*)realloc(hp-_a, newcapacity * sizeof(HPDataType));if (tmp NULL) {perror(realloc fail);exit(-1);}hp-_a tmp;hp-_capacity newcapacity;}hp-_a[hp-_size] x;hp-_size;AdjustUp(hp, hp-_size - 1);
}void HeapCreate(Heap* hp, HPDataType* a, int n) {assert(hp);HeapInit(hp); //初始化为空堆for (int i 0; i n; i) {HeapPush(hp, a[i]);}
}由于向上调整的效率不及向下调整所以建议采用向下调整建堆 向下调整要求左子树和右子树也都是堆又因为单个叶子结点既可以看作是大堆也可以看成小堆所以我们从叶子结点的双亲开始向下调整
比如下面这个数组要建一个大堆
int a[] {4,3,5,7,2,6,8,65,100,70,32,50,60};调整后红色方框内就是一个大堆了对于3,5这两个结点而言左右子树都是大堆那它们也可以向下调整了 代码如下
void HeapCreate(Heap* hp, HPDataType* a, int n) {assert(hp);HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType) * n);if (tmp NULL) {perror(malloc fail);exit(-1);}hp-_a tmp;hp-_capacity hp-_size n;memcpy(hp-_a, a, n * sizeof(HPDataType)); //把数组数据拷贝到堆的数组中int parent (hp-_size - 1 - 1) / 2; //最后一个结点的双亲结点for (int i parent; i 0;i--) { //从该结点开始进行向下调整AdjustDown(hp-_a, n, i);}
}堆排序
现在有一个数组要把它排成升序 如果建小堆那么很容易就可以找到最小的元素。但是要找次小元素的时候把数组剩下的元素看作完全二叉树的话它们之间的关系会乱掉
●所以要建大堆建好后最大的元素就在根结点将它和最后一个结点交换就把最大的元素排好了 ●然后size-1剔除最大的元素对于剩下的元素因为根结点的左右子树也都是大堆可以采用向下调整调整后可以把第二大的元素移动到堆顶根结点再和最后一个结点交换第二大元素就排好了 ●剩下的元素也如法炮制
void HeapSort(int* a, int k) { //a为给定数组for (int i (k - 1 - 1) / 2; i 0; i--) { //调整为一个堆AdjustDown(a, k, i);}for (int i k - 1; i 0; i--) { //采用删除结点的思想先交换再调整Swap(a[0], a[i]);AdjustDown(a, i, 0);}
}排序后得到 top k 问题
这个问题就是要找出数组中从大到小或从小到大的前k个数下面以从大到小为例 如果要找从大到小的前k个数我们可以先从数组中选k个数建一个大小为k的小堆然后将数组中剩下的数和堆顶的数进行比较如果比它大就替代它然后向下调整。 这个方法的原理是放一个比较小的数“卡”在堆顶类似守门员比它大的数就能进堆不断把堆中较小的数踢出去到最后就留下最大的前k个数
//取最大的前k个
void TopK(HPDataType* pa, int n, int k) {Heap ph;HeapInit(ph);HeapCreate1(ph, pa, k); //建小堆for (int i k; i n; i) //遍历剩下的元素{if (pa[i] ph._a[0]) {ph._a[0] pa[i];AdjustDown(ph._a, k, 0); //小堆向下调整}}HeapSort(ph._a, k); //将得到前k数进行排序HeapPrint(ph);
}写在最后
以上就是本篇文章的全部内容如果你觉得本文对你有所帮助的话那不妨点个小小的赞哦比心
