没有孩子的结点就是叶子结点树是由递归定义的树是由根和子树组成,子树又是由根和子树组成,不断往下套娃,最终形成树树的存储表示 ----左孩子右兄弟表示法在树结点里面就储存三个东西 :指向这个结点从左往右数第一个孩子的指针指向这个结点右边第一个亲兄弟的指针结点本身的数值树节点代码 :structTreeNode{intval;structTreeNode*leftchild;// 左孩子structTreeNode*rightbrother;// 左孩子的右兄弟};这个结构最巧妙的地方在于 :不管有多少个孩子,我只指向从左往右数第一个孩子, 其他的孩子用第一个孩子去找如何找孩子?先给定一个父节点,再定义一个遍历指针指针里面存储父节点的第一个孩子的地址,通过不断遍历每一个孩子的右兄弟,进而找到所有孩子找孩子的代码 :TreeNode*parent;// 先给定一个父节点TreeNode*cur;// 定义遍历的指针curparent-leftChild;// 指针指向第一个孩子while(cur){// 打印...curcur-rightbrother;// 遍历每一个孩子的右兄弟}二叉树就是每个结点最多有两个孩子一个 h 层的满二叉树可以存储 2^h-1 个结点完全二叉树就是在满二叉树的基础上,在最后一层的叶子结点上,从右往左依次删除若干个结点,剩下的就是完全二叉树什么是堆?堆是一棵满足父节点与子节点大小规则的完全二叉树堆分为大根堆和小根堆大根堆的核心特点-----每个父节点的值都大于等于其所有孩子结点的值小根堆的核心特点-----每个父节点的值都小于等于其所有孩子结点的值堆可以执行删除任意元素的操作,但是堆的设计初衷是高效操作堆顶元素(最值),删除任意元素需要额外处理,且时间复杂度会比删除堆顶元素高堆的逻辑结构上是一棵树,物理结构上是一个数组( 这个数组各个位置元素的摆放规律依照完全二叉树自顶向下,从左往右一层一层的元素顺序设置的 )既然底层用数组实现堆,那么就要关心扩容问题所以,定义堆的结构体包含三个要素 :指向数组的指针当前数组的有效元素 ( 也恰好标记了数组中最后一个元素下一位的坐标)数组的最大容量typedefintHPDataType;structHeap{HPDataType*a;intsize;intcapacity;};typedefstructHeapHP;堆的接口 初始化和销毁堆结构体里的指针置空,有效元素个数和数组容量置为0销毁多了一个释放动态开辟的数组的空间// 初始化voidHPInit(HP*php){assert(php);php-aNULL;php-sizephp-capacity0;}// 销毁voidHPDestory(HP*php){assert(php);free(php-a);php-aNULL;php-sizephp-capacity0;} 堆的插入先在数组尾部插入一个数据( 插入数据前别忘了检查是否需要扩容 ) , 再用向上调整算法看看是否需要调整位置先往空数组里插入一个数据,然后调整位置;再在数组里插入一个数据,然后调整位置…不断循环往复 , 大 or 小 根堆就建出来了 向上调整算法 (小根堆) :将新插入数组的元素视为孩子结点,用孩子结点在数组里的下标计算 ta 的父节点下标,对比孩子结点与父节点的值如果孩子结点的值小于父亲结点,交换两结点的值,将旧的父亲结点变为新的孩子结点,然后计算新的父节点下标,再进行比较…直到孩子结点变到根结点位置( 孩子结点的下标变为0 )如果孩子结点的值大于父亲结点,不用调整// 向上调整算法---建小堆voidAdjustUp(Heap*hp,intchild)// 传的参数为 指向堆结构体的指针 孩子结点对应的数组下标{assert(hp);while(child){// 先计算父节点的下标intparent(child-1)/2;// 对比孩子结点和父节点的数值// 当孩子结点 父节点数值if(hp-_a[child]hp-_a[parent]){// 交换数值Swap((hp-_a[child]),(hp-_a[parent]));// 旧父母变成新孩子childparent;}// 当孩子结点 ≥ 父节点数值else{// 小根堆性质恢复,跳出循环break;}}}交换父子结点里的数值 :形参的改变要想影响实参,需要传实参的地址.所以交换函数的参数传递的是数组中对应父子结点值的地址// 交换函数voidSwap(HPDataType*p1,HPDataType*p2){HPDataType tmp*p1;// *p1是数组对应下标里存的元素值*p1*p2;*p2tmp;}堆插入的代码 :// 堆的插入voidHPPush(HP*php,HPDataType x)// 传的参数为指向堆结构体的指针 以及 插入的元素{// 插入数据前先判断是否需要扩容if(php-sizephp-capacity){intnewcapacityphp-capacity0?4:2*php-capacity;HPDataType*tmp(HPDataType*)realloc(php-a,newcapacity*sizeof(HPDataType));if(tmpNULL)// 处理开辟失败{perror(realloc fail);return;}else// 开辟成功{php-atmp;php-capacitynewcapacity;}}php-a[php-size]x;php-size;// 先往数组里面插入一个元素,然后再向上调整AdjustUp(php-a,php-size-1);} 堆的删除堆的删除,一般指的是删除堆顶元素不可以对数组中的元素进行挪动从而删除堆顶数据( 堆顶数据对应数组中下标为0位置的元素 ) , 因为这样会导致父子关系乱套这里要实现堆顶元素的删除 , 可以先将数组首尾元素换位 , 然后再删除掉数组尾元素这么做的好处有 :最大程度维持了堆中父子关系的正确性,顶多就是堆顶元素不正确,但是其他分支依然正确数组尾部元素的删除操作简单,直接size- - 就完事了那么 , 如何处理堆顶元素父子关系不正确的问题 ?这里就要用到向下调整算法 向下调整算法 (小根堆) :假设左孩子为最小孩子, 利用父节点下标 parent 计算 ta 的左孩子下标当左孩子存在时,进入循环当右孩子存在时,先验证假设的正确性再来对比父节点和最小孩子结点的数值如果父结点值 最小孩子的值交换双方的数值 , 最小孩子变成新父亲, 重新假设并计算新的最小孩子下标如果父结点的值 ≤ 最小孩子的值 : 此时堆性质恢复,跳出循环向下调整算法 代码展示 :// 向下调整算法---建小堆voidAdjustDown(Heap*hp,intparent){assert(hp);intminchildparent*21;// 先假设左孩子是最小孩子while(minchildhp-_size)// 先保证左孩子存在{// 如果右孩子存在,先验证左孩子是否为最小孩子if(minchild1hp-_size){if(hp-_a[minchild]hp-_a[minchild1]){minchild;// 最小孩子变为右孩子}}// 对比父节点和最小孩子结点// 父亲结点数值 最小孩子结点数值if(hp-_a[parent]hp-_a[minchild]){// 交换父亲与最小孩子结点的数值Swap((hp-_a[parent]),(hp-_a[minchild]));// 旧孩子变新父亲parentminchild;// 重新假设计算最小孩子下标minchildparent*21;}// 父亲结点数值 ≤ 最小孩子结点数值else{// 已维持小根堆特性,不用再进行调整break;}}}向下调整算法需要对比两个孩子,向上调整算法只需要对比一个父亲删除堆顶元素 代码展示 :// 删除堆顶元素voidHPPop(HP*php){assert(php);// 后续需要对其进行解引用assert(php-size0);// 保证数组里有东西可以删除Swap((php-a[0]),(php-a[php-size-1]));// 交换数组首尾元素php-size--;AdjustDown(php-a,php-size,0);// 向下调整}堆删除的时间复杂度为 logN时间复杂度算的是循环次数,删除操作交换首尾和size- - 都可以不计算,唯一有循环味道的是向下调整的次数最坏情况就是调整了整个堆的高度一个含有 N 个结点的堆 , ta 的高度为logN最坏调整了 logN 次所以 ta 的时间复杂度为 logN 返回堆顶元素返回数组里面的第一个元素// 返回堆顶的元素HPDataTypeHPTop(HP*php){assert(php);assert(php-size0);returnphp-a[0];} 判空返回数组的有效元素个数是否等于0// 判空boolHPEmpty(HP*php){assert(php);returnphp-size0;} 堆排序 ( 数组元素 )若要对数组中数据进行降序排序,建堆时推荐建立小堆若要对数组中数据进行升序排序,建堆时推荐建立大堆调整算法里面的比较逻辑决定了建的堆是大堆还是小堆核心 ----- 先反着建堆,不断找出最值,首尾元素交换,再进行调整 第一步 ---- 建堆 第一种建堆方式 — 向上调整建堆遍历数组中第二个到最后一个元素,每一次遍历都对该元素进行一次向上调整,从而完成建小根堆的过程 第二种建堆方式 — 向下调整建堆从倒数的第一个非叶结点开始调从数组中最后一个元素入手,算出 ta 的父节点下标,从这个下标开始,向下调整一次… 下标每往前移动一个单位,就向下调整一次… 不断循环往复进而完成建堆 第二步 ---- 排序 ( 假设已经建好小堆 )交换数组中首尾元素位置,交换后数组中最后一个元素为最小元素然后再对堆顶元素进行向下调整( 注意此时数组中最后一个元素已然完成排序,不纳入调整 ) , 进而找出次小的元素由于数组中最后一个元素已经排好序不纳入调整,所以数组里的有效个数要先 -1 才能进入下一个循环然后再交换数组中首尾元素位置…不断循环往复// 堆排序 --- 降序voidHeapSort(HP*hp){// step1.--- 向下调整建小堆intparent(hp-size-1-1)/2;for(intiparent;i0;i--){AdjustDown(hp,i);}// step2.--- 排序// 数组里有效元素个数至少2个,交换才有意义while(hp-size1){// 交换数组中首尾元素Swap((hp-a[0]),(hp-a[hp-size-1]));// 此时数组最后一个元素为数组里面的最小值(符合降序要求)// 由于交换后数组首元素不符合堆的性质,要进行调整// 为了保证向下调整时不动数组里已经排好序的元素// 数组中的有效元素个数需要-1hp-size--;// 对首元素进行向下调整AdjustDown(hp,0);}} 分析 step1-1 向下调整法建堆 的时间复杂度调整的次数跟高度有关,每一层结点的数量跟高度有关假设完全二叉树的结点个数为 N ,树高为 h无论建立的是小根堆还是大根堆,树的最后一层 ( 第h层 ) 结点都不需要调,实际的调整范围是从倒数第二层 ( 第h-1层 ) 开始的第 h-1 层共有 2(h-2)个结点,最坏情况是这一层的每一个结点都要往下调 1 层.共计调了 1*2(h-2)次第 h-2 层共有2(h-3)个结点,最坏情况是这一层的每一个结点都往下调 2 层.共计调了 2*2(h-3)次以此类推…第 2 层共有21个结点,最坏情况是这一层的每一个结点都要往下调 h-2 层.共计调了 (h-2)*21次第 1 层共有20个结点,最坏情况是这一层的每一个结点都要往下调 h-1 层.共计调了 (h-1)*20次所以 ,总共的调整次数其实是关于 层高 h 的函数总调整次数 :T ( h ) 2 0 ( h − 1 ) 2 1 ( h − 2 ) 2 2 ( h − 3 ) 2 3 ( h − 4 ) ⋯ 2 h − 3 ⋅ 2 2 h − 2 ⋅ 1 (1) T(h)2^0(h-1)2^1(h-2)2^2(h-3)2^3(h-4)\dots2^{h-3}\cdot 22^{h-2}\cdot 1 \tag{1}T(h)20(h−1)21(h−2)22(h−3)23(h−4)⋯2h−3⋅22h−2⋅1(1)经典的 等差 * 等比 用错位相减法求解一般来讲 , 研究二叉树最后结论都要往结点个数上面去靠拢 , 所以接下来研究 节点个数与层高 h 的关系 ,进而将 总调整次数 转化为关于总结点个数的函数以满二叉树来举例:第 1 层共有 20个结点第 2 层共有 21个结点以此类推…第 h-1 层共有 2h-2个结点第 h 层共有 2h-1个结点不妨设总共的结点数为 N则有 :N 2 0 2 1 2 2 ⋯ 2 h − 2 2 h − 1 N2^02^12^2\dots2^{h-2}2^{h-1}N202122⋯2h−22h−1可得 :N 2 h − 1 , h log 2 ( N 1 ) N2^h-1,\quad h\log_2(N1)N2h−1,hlog2(N1)所以所以,向下调整法建堆的时间复杂度为 O ( N )时间复杂度只保留影响最大的那个项 分析 step1-2 向上调整法建堆 的时间复杂度假设完全二叉树的结点个数为 N ,树高为 h向上调整法建堆,调整是从第二层开始的第 2 层共有 21个元素,最坏情况所有元素都要往上调 1 层.共调 1*21次第 3 层共有 22个元素,最坏情况每个元素都熬往上调 2 层.共调 2*22次以此类推…第 h-1 层共有2h-2个元素,最坏情况每个元素都要往上调 h-2 层.共调 (h-2)*2h-2次第 h 层共有 2h-1个元素,最坏情况每个元素都要往上调 h-1 层.共调 (h-1)*2h-1次所以 , 总的调整次数 :T ( h ) 2 1 ⋅ 1 2 2 ⋅ 2 ⋯ 2 h − 2 ⋅ ( h − 2 ) 2 h − 1 ⋅ ( h − 1 ) T(h) 2^1 \cdot 1 2^2 \cdot 2 \dots 2^{h-2} \cdot (h-2) 2^{h-1} \cdot (h-1)T(h)21⋅122⋅2⋯2h−2⋅(h−2)2h−1⋅(h−1)化简 :T ( h ) − ( 2 0 2 1 2 2 ⋯ 2 h − 1 ) 2 h ⋅ ( h − 1 ) 2 0 T(h) -\left(2^0 2^1 2^2 \dots 2^{h-1}\right) 2^h \cdot (h-1) 2^0T(h)−(202122⋯2h−1)2h⋅(h−1)20又由 满二叉树层高与结点个数换算公式 :N 2 h − 1 , h log 2 ( N 1 ) N2^h-1,\quad h\log_2(N1)N2h−1,hlog2(N1)可得 :T ( N ) − N ( N 1 ) ⋅ ( log 2 ( N 1 ) − 1 ) 1 T(N) -N (N1)\cdot\big(\log_2(N1)-1\big) 1T(N)−N(N1)⋅(log2(N1)−1)1所以 ,向上调整法建堆的时间复杂度为 O ( N * logN )所以,在进行建堆时,向下调整算法明显优于向上调整算法 分析 step2. 排序 的时间复杂度从结点最多的最后一层分析最后一层的结点数量为 2h-1个交换数组首尾元素后,最坏情况是要往下调 h-1 层所以,最后一层的结点最坏情况下,总的调整次数为 2h-1*(h-1) 次又由 满二叉树层高与结点个数换算公式 :N 2 h − 1 , h log 2 ( N 1 ) N2^h-1,\quad h\log_2(N1)N2h−1,hlog2(N1)可知 :2 h − 1 ( h − 1 ) 2 log 2 ( h 1 ) − 1 2^{h-1}(h-1) 2^{\log_2(h1)-1}2h−1(h−1)2log2(h1)−1则有 :所以,最后一层排序的时间复杂度为 N*logN因为最后一层结点最多,对总的调整次数影响最大,所以这个step2.排序 的时间复杂度就是 O ( N*logN )
没有孩子的结点就是叶子结点树是由递归定义的树是由根和子树组成,子树又是由根和子树组成,不断往下套娃,最终形成树树的存储表示 ----左孩子右兄弟表示法在树结点里面就储存三个东西 :指向这个结点从左往右数第一个孩子的指针指向这个结点右边第一个亲兄弟的指针结点本身的数值树节点代码 :structTreeNode{intval;structTreeNode*leftchild;// 左孩子structTreeNode*rightbrother;// 左孩子的右兄弟};这个结构最巧妙的地方在于 :不管有多少个孩子,我只指向从左往右数第一个孩子, 其他的孩子用第一个孩子去找如何找孩子?先给定一个父节点,再定义一个遍历指针指针里面存储父节点的第一个孩子的地址,通过不断遍历每一个孩子的右兄弟,进而找到所有孩子找孩子的代码 :TreeNode*parent;// 先给定一个父节点TreeNode*cur;// 定义遍历的指针curparent-leftChild;// 指针指向第一个孩子while(cur){// 打印...curcur-rightbrother;// 遍历每一个孩子的右兄弟}二叉树就是每个结点最多有两个孩子一个 h 层的满二叉树可以存储 2^h-1 个结点完全二叉树就是在满二叉树的基础上,在最后一层的叶子结点上,从右往左依次删除若干个结点,剩下的就是完全二叉树什么是堆?堆是一棵满足父节点与子节点大小规则的完全二叉树堆分为大根堆和小根堆大根堆的核心特点-----每个父节点的值都大于等于其所有孩子结点的值小根堆的核心特点-----每个父节点的值都小于等于其所有孩子结点的值堆可以执行删除任意元素的操作,但是堆的设计初衷是高效操作堆顶元素(最值),删除任意元素需要额外处理,且时间复杂度会比删除堆顶元素高堆的逻辑结构上是一棵树,物理结构上是一个数组( 这个数组各个位置元素的摆放规律依照完全二叉树自顶向下,从左往右一层一层的元素顺序设置的 )既然底层用数组实现堆,那么就要关心扩容问题所以,定义堆的结构体包含三个要素 :指向数组的指针当前数组的有效元素 ( 也恰好标记了数组中最后一个元素下一位的坐标)数组的最大容量typedefintHPDataType;structHeap{HPDataType*a;intsize;intcapacity;};typedefstructHeapHP;堆的接口 初始化和销毁堆结构体里的指针置空,有效元素个数和数组容量置为0销毁多了一个释放动态开辟的数组的空间// 初始化voidHPInit(HP*php){assert(php);php-aNULL;php-sizephp-capacity0;}// 销毁voidHPDestory(HP*php){assert(php);free(php-a);php-aNULL;php-sizephp-capacity0;} 堆的插入先在数组尾部插入一个数据( 插入数据前别忘了检查是否需要扩容 ) , 再用向上调整算法看看是否需要调整位置先往空数组里插入一个数据,然后调整位置;再在数组里插入一个数据,然后调整位置…不断循环往复 , 大 or 小 根堆就建出来了 向上调整算法 (小根堆) :将新插入数组的元素视为孩子结点,用孩子结点在数组里的下标计算 ta 的父节点下标,对比孩子结点与父节点的值如果孩子结点的值小于父亲结点,交换两结点的值,将旧的父亲结点变为新的孩子结点,然后计算新的父节点下标,再进行比较…直到孩子结点变到根结点位置( 孩子结点的下标变为0 )如果孩子结点的值大于父亲结点,不用调整// 向上调整算法---建小堆voidAdjustUp(Heap*hp,intchild)// 传的参数为 指向堆结构体的指针 孩子结点对应的数组下标{assert(hp);while(child){// 先计算父节点的下标intparent(child-1)/2;// 对比孩子结点和父节点的数值// 当孩子结点 父节点数值if(hp-_a[child]hp-_a[parent]){// 交换数值Swap((hp-_a[child]),(hp-_a[parent]));// 旧父母变成新孩子childparent;}// 当孩子结点 ≥ 父节点数值else{// 小根堆性质恢复,跳出循环break;}}}交换父子结点里的数值 :形参的改变要想影响实参,需要传实参的地址.所以交换函数的参数传递的是数组中对应父子结点值的地址// 交换函数voidSwap(HPDataType*p1,HPDataType*p2){HPDataType tmp*p1;// *p1是数组对应下标里存的元素值*p1*p2;*p2tmp;}堆插入的代码 :// 堆的插入voidHPPush(HP*php,HPDataType x)// 传的参数为指向堆结构体的指针 以及 插入的元素{// 插入数据前先判断是否需要扩容if(php-sizephp-capacity){intnewcapacityphp-capacity0?4:2*php-capacity;HPDataType*tmp(HPDataType*)realloc(php-a,newcapacity*sizeof(HPDataType));if(tmpNULL)// 处理开辟失败{perror(realloc fail);return;}else// 开辟成功{php-atmp;php-capacitynewcapacity;}}php-a[php-size]x;php-size;// 先往数组里面插入一个元素,然后再向上调整AdjustUp(php-a,php-size-1);} 堆的删除堆的删除,一般指的是删除堆顶元素不可以对数组中的元素进行挪动从而删除堆顶数据( 堆顶数据对应数组中下标为0位置的元素 ) , 因为这样会导致父子关系乱套这里要实现堆顶元素的删除 , 可以先将数组首尾元素换位 , 然后再删除掉数组尾元素这么做的好处有 :最大程度维持了堆中父子关系的正确性,顶多就是堆顶元素不正确,但是其他分支依然正确数组尾部元素的删除操作简单,直接size- - 就完事了那么 , 如何处理堆顶元素父子关系不正确的问题 ?这里就要用到向下调整算法 向下调整算法 (小根堆) :假设左孩子为最小孩子, 利用父节点下标 parent 计算 ta 的左孩子下标当左孩子存在时,进入循环当右孩子存在时,先验证假设的正确性再来对比父节点和最小孩子结点的数值如果父结点值 最小孩子的值交换双方的数值 , 最小孩子变成新父亲, 重新假设并计算新的最小孩子下标如果父结点的值 ≤ 最小孩子的值 : 此时堆性质恢复,跳出循环向下调整算法 代码展示 :// 向下调整算法---建小堆voidAdjustDown(Heap*hp,intparent){assert(hp);intminchildparent*21;// 先假设左孩子是最小孩子while(minchildhp-_size)// 先保证左孩子存在{// 如果右孩子存在,先验证左孩子是否为最小孩子if(minchild1hp-_size){if(hp-_a[minchild]hp-_a[minchild1]){minchild;// 最小孩子变为右孩子}}// 对比父节点和最小孩子结点// 父亲结点数值 最小孩子结点数值if(hp-_a[parent]hp-_a[minchild]){// 交换父亲与最小孩子结点的数值Swap((hp-_a[parent]),(hp-_a[minchild]));// 旧孩子变新父亲parentminchild;// 重新假设计算最小孩子下标minchildparent*21;}// 父亲结点数值 ≤ 最小孩子结点数值else{// 已维持小根堆特性,不用再进行调整break;}}}向下调整算法需要对比两个孩子,向上调整算法只需要对比一个父亲删除堆顶元素 代码展示 :// 删除堆顶元素voidHPPop(HP*php){assert(php);// 后续需要对其进行解引用assert(php-size0);// 保证数组里有东西可以删除Swap((php-a[0]),(php-a[php-size-1]));// 交换数组首尾元素php-size--;AdjustDown(php-a,php-size,0);// 向下调整}堆删除的时间复杂度为 logN时间复杂度算的是循环次数,删除操作交换首尾和size- - 都可以不计算,唯一有循环味道的是向下调整的次数最坏情况就是调整了整个堆的高度一个含有 N 个结点的堆 , ta 的高度为logN最坏调整了 logN 次所以 ta 的时间复杂度为 logN 返回堆顶元素返回数组里面的第一个元素// 返回堆顶的元素HPDataTypeHPTop(HP*php){assert(php);assert(php-size0);returnphp-a[0];} 判空返回数组的有效元素个数是否等于0// 判空boolHPEmpty(HP*php){assert(php);returnphp-size0;} 堆排序 ( 数组元素 )若要对数组中数据进行降序排序,建堆时推荐建立小堆若要对数组中数据进行升序排序,建堆时推荐建立大堆调整算法里面的比较逻辑决定了建的堆是大堆还是小堆核心 ----- 先反着建堆,不断找出最值,首尾元素交换,再进行调整 第一步 ---- 建堆 第一种建堆方式 — 向上调整建堆遍历数组中第二个到最后一个元素,每一次遍历都对该元素进行一次向上调整,从而完成建小根堆的过程 第二种建堆方式 — 向下调整建堆从倒数的第一个非叶结点开始调从数组中最后一个元素入手,算出 ta 的父节点下标,从这个下标开始,向下调整一次… 下标每往前移动一个单位,就向下调整一次… 不断循环往复进而完成建堆 第二步 ---- 排序 ( 假设已经建好小堆 )交换数组中首尾元素位置,交换后数组中最后一个元素为最小元素然后再对堆顶元素进行向下调整( 注意此时数组中最后一个元素已然完成排序,不纳入调整 ) , 进而找出次小的元素由于数组中最后一个元素已经排好序不纳入调整,所以数组里的有效个数要先 -1 才能进入下一个循环然后再交换数组中首尾元素位置…不断循环往复// 堆排序 --- 降序voidHeapSort(HP*hp){// step1.--- 向下调整建小堆intparent(hp-size-1-1)/2;for(intiparent;i0;i--){AdjustDown(hp,i);}// step2.--- 排序// 数组里有效元素个数至少2个,交换才有意义while(hp-size1){// 交换数组中首尾元素Swap((hp-a[0]),(hp-a[hp-size-1]));// 此时数组最后一个元素为数组里面的最小值(符合降序要求)// 由于交换后数组首元素不符合堆的性质,要进行调整// 为了保证向下调整时不动数组里已经排好序的元素// 数组中的有效元素个数需要-1hp-size--;// 对首元素进行向下调整AdjustDown(hp,0);}} 分析 step1-1 向下调整法建堆 的时间复杂度调整的次数跟高度有关,每一层结点的数量跟高度有关假设完全二叉树的结点个数为 N ,树高为 h无论建立的是小根堆还是大根堆,树的最后一层 ( 第h层 ) 结点都不需要调,实际的调整范围是从倒数第二层 ( 第h-1层 ) 开始的第 h-1 层共有 2(h-2)个结点,最坏情况是这一层的每一个结点都要往下调 1 层.共计调了 1*2(h-2)次第 h-2 层共有2(h-3)个结点,最坏情况是这一层的每一个结点都往下调 2 层.共计调了 2*2(h-3)次以此类推…第 2 层共有21个结点,最坏情况是这一层的每一个结点都要往下调 h-2 层.共计调了 (h-2)*21次第 1 层共有20个结点,最坏情况是这一层的每一个结点都要往下调 h-1 层.共计调了 (h-1)*20次所以 ,总共的调整次数其实是关于 层高 h 的函数总调整次数 :T ( h ) 2 0 ( h − 1 ) 2 1 ( h − 2 ) 2 2 ( h − 3 ) 2 3 ( h − 4 ) ⋯ 2 h − 3 ⋅ 2 2 h − 2 ⋅ 1 (1) T(h)2^0(h-1)2^1(h-2)2^2(h-3)2^3(h-4)\dots2^{h-3}\cdot 22^{h-2}\cdot 1 \tag{1}T(h)20(h−1)21(h−2)22(h−3)23(h−4)⋯2h−3⋅22h−2⋅1(1)经典的 等差 * 等比 用错位相减法求解一般来讲 , 研究二叉树最后结论都要往结点个数上面去靠拢 , 所以接下来研究 节点个数与层高 h 的关系 ,进而将 总调整次数 转化为关于总结点个数的函数以满二叉树来举例:第 1 层共有 20个结点第 2 层共有 21个结点以此类推…第 h-1 层共有 2h-2个结点第 h 层共有 2h-1个结点不妨设总共的结点数为 N则有 :N 2 0 2 1 2 2 ⋯ 2 h − 2 2 h − 1 N2^02^12^2\dots2^{h-2}2^{h-1}N202122⋯2h−22h−1可得 :N 2 h − 1 , h log 2 ( N 1 ) N2^h-1,\quad h\log_2(N1)N2h−1,hlog2(N1)所以所以,向下调整法建堆的时间复杂度为 O ( N )时间复杂度只保留影响最大的那个项 分析 step1-2 向上调整法建堆 的时间复杂度假设完全二叉树的结点个数为 N ,树高为 h向上调整法建堆,调整是从第二层开始的第 2 层共有 21个元素,最坏情况所有元素都要往上调 1 层.共调 1*21次第 3 层共有 22个元素,最坏情况每个元素都熬往上调 2 层.共调 2*22次以此类推…第 h-1 层共有2h-2个元素,最坏情况每个元素都要往上调 h-2 层.共调 (h-2)*2h-2次第 h 层共有 2h-1个元素,最坏情况每个元素都要往上调 h-1 层.共调 (h-1)*2h-1次所以 , 总的调整次数 :T ( h ) 2 1 ⋅ 1 2 2 ⋅ 2 ⋯ 2 h − 2 ⋅ ( h − 2 ) 2 h − 1 ⋅ ( h − 1 ) T(h) 2^1 \cdot 1 2^2 \cdot 2 \dots 2^{h-2} \cdot (h-2) 2^{h-1} \cdot (h-1)T(h)21⋅122⋅2⋯2h−2⋅(h−2)2h−1⋅(h−1)化简 :T ( h ) − ( 2 0 2 1 2 2 ⋯ 2 h − 1 ) 2 h ⋅ ( h − 1 ) 2 0 T(h) -\left(2^0 2^1 2^2 \dots 2^{h-1}\right) 2^h \cdot (h-1) 2^0T(h)−(202122⋯2h−1)2h⋅(h−1)20又由 满二叉树层高与结点个数换算公式 :N 2 h − 1 , h log 2 ( N 1 ) N2^h-1,\quad h\log_2(N1)N2h−1,hlog2(N1)可得 :T ( N ) − N ( N 1 ) ⋅ ( log 2 ( N 1 ) − 1 ) 1 T(N) -N (N1)\cdot\big(\log_2(N1)-1\big) 1T(N)−N(N1)⋅(log2(N1)−1)1所以 ,向上调整法建堆的时间复杂度为 O ( N * logN )所以,在进行建堆时,向下调整算法明显优于向上调整算法 分析 step2. 排序 的时间复杂度从结点最多的最后一层分析最后一层的结点数量为 2h-1个交换数组首尾元素后,最坏情况是要往下调 h-1 层所以,最后一层的结点最坏情况下,总的调整次数为 2h-1*(h-1) 次又由 满二叉树层高与结点个数换算公式 :N 2 h − 1 , h log 2 ( N 1 ) N2^h-1,\quad h\log_2(N1)N2h−1,hlog2(N1)可知 :2 h − 1 ( h − 1 ) 2 log 2 ( h 1 ) − 1 2^{h-1}(h-1) 2^{\log_2(h1)-1}2h−1(h−1)2log2(h1)−1则有 :所以,最后一层排序的时间复杂度为 N*logN因为最后一层结点最多,对总的调整次数影响最大,所以这个step2.排序 的时间复杂度就是 O ( N*logN )
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
