企业官网建设流程全解析

没有孩子的结点就是叶子结点

树是由递归定义的
树是由根和子树组成,子树又是由根和子树组成,不断往下套娃,最终形成树

---

树的存储表示 ----左孩子右兄弟表示法

在树结点里面就储存三个东西 :

• 指向这个结点从左往右数第一个孩子的指针
• 指向这个结点右边第一个亲兄弟的指针
• 结点本身的数值

树节点代码 :

structTreeNode{intval;structTreeNode*leftchild;// 左孩子structTreeNode*rightbrother;// 左孩子的右兄弟};

这个结构最巧妙的地方在于 :

不管有多少个孩子,我只指向从左往右数第一个孩子, 其他的孩子用第一个孩子去找

如何找孩子?
先给定一个父节点,再定义一个遍历指针

指针里面存储父节点的第一个孩子的地址,通过不断遍历每一个孩子的右兄弟,进而找到所有孩子

找孩子的代码 :

TreeNode*parent;// 先给定一个父节点TreeNode*cur;// 定义遍历的指针cur=parent->leftChild;// 指针指向第一个孩子while(cur){// 打印...cur=cur->rightbrother;// 遍历每一个孩子的右兄弟}

---

二叉树就是每个结点最多有两个孩子

一个 h 层的满二叉树可以存储 2^h-1 个结点

完全二叉树就是在满二叉树的基础上,在最后一层的叶子结点上,从右往左依次删除若干个结点,剩下的就是完全二叉树

---

---

什么是堆?

• 堆是一棵满足父节点与子节点大小规则的完全二叉树
• 堆分为大根堆和小根堆
  • 大根堆的核心特点-----每个父节点的值都大于等于其所有孩子结点的值
  • 小根堆的核心特点-----每个父节点的值都小于等于其所有孩子结点的值
• 堆可以执行删除任意元素的操作,但是堆的设计初衷是高效操作堆顶元素(最值),删除任意元素需要额外处理,且时间复杂度会比删除堆顶元素高

堆的逻辑结构上是一棵树,物理结构上是一个数组( 这个数组各个位置元素的摆放规律依照完全二叉树自顶向下,从左往右一层一层的元素顺序设置的 )

既然底层用数组实现堆,那么就要关心扩容问题

所以,定义堆的结构体包含三个要素 :

• 指向数组的指针
• 当前数组的有效元素 ( 也恰好标记了数组中最后一个元素下一位的坐标)
• 数组的最大容量

typedefintHPDataType;structHeap{HPDataType*a;intsize;intcapacity;};typedefstructHeapHP;

---

堆的接口

🐛 初始化和销毁

堆结构体里的指针置空,有效元素个数和数组容量置为0

销毁多了一个释放动态开辟的数组的空间

// 初始化voidHPInit(HP*php){assert(php);php->a=NULL;php->size=php->capacity=0;}// 销毁voidHPDestory(HP*php){assert(php);free(php->a);php->a=NULL;php->size=php->capacity=0;}

🐛 堆的插入

先在数组尾部插入一个数据( 插入数据前别忘了检查是否需要扩容 ) , 再用向上调整算法看看是否需要调整位置

先往空数组里插入一个数据,然后调整位置;再在数组里插入一个数据,然后调整位置…不断循环往复 , 大 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]));// 旧父母变成新孩子child=parent;}// 当孩子结点 ≥ 父节点数值else{// 小根堆性质恢复,跳出循环break;}}}

交换父子结点里的数值 :

形参的改变要想影响实参,需要传实参的地址.所以交换函数的参数传递的是数组中对应父子结点值的地址

// 交换函数voidSwap(HPDataType*p1,HPDataType*p2){HPDataType tmp=*p1;// *p1是数组对应下标里存的元素值*p1=*p2;*p2=tmp;}

堆插入的代码 :

// 堆的插入voidHPPush(HP*php,HPDataType x)// 传的参数为指向堆结构体的指针 以及 插入的元素{// 插入数据前先判断是否需要扩容if(php->size==php->capacity){intnewcapacity=php->capacity==0?4:2*php->capacity;HPDataType*tmp=(HPDataType*)realloc(php->a,newcapacity*sizeof(HPDataType));if(tmp==NULL)// 处理开辟失败{perror("realloc fail");return;}else// 开辟成功{php->a=tmp;php->capacity=newcapacity;}}php->a[php->size]=x;php->size++;// 先往数组里面插入一个元素,然后再向上调整AdjustUp(php->a,php->size-1);}

🐛 堆的删除

堆的删除,一般指的是删除堆顶元素

不可以对数组中的元素进行挪动从而删除堆顶数据( 堆顶数据对应数组中下标为0位置的元素 ) , 因为这样会导致父子关系乱套

这里要实现堆顶元素的删除 , 可以先将数组首尾元素换位 , 然后再删除掉数组尾元素

这么做的好处有 :

• 最大程度维持了堆中父子关系的正确性,顶多就是堆顶元素不正确,但是其他分支依然正确
• 数组尾部元素的删除操作简单,直接size- - 就完事了

那么 , 如何处理堆顶元素父子关系不正确的问题 ?

这里就要用到向下调整算法

🌸 向下调整算法 (小根堆) :

• 假设左孩子为最小孩子, 利用父节点下标 parent 计算 ta 的左孩子下标
• 当左孩子存在时,进入循环
• 当右孩子存在时,先验证假设的正确性
• 再来对比父节点和最小孩子结点的数值
  • 如果父结点值 ＞ 最小孩子的值：交换双方的数值 , 最小孩子变成新父亲, 重新假设并计算新的最小孩子下标
  • 如果父结点的值 ≤ 最小孩子的值 : 此时堆性质恢复,跳出循环

向下调整算法 代码展示 :

// 向下调整算法---建小堆voidAdjustDown(Heap*hp,intparent){assert(hp);intminchild=parent*2+1;// 先假设左孩子是最小孩子while(minchild<hp->_size)// 先保证左孩子存在{// 如果右孩子存在,先验证左孩子是否为最小孩子if(minchild+1<hp->_size){if(hp->_a[minchild]>hp->_a[minchild+1]){minchild++;// 最小孩子变为右孩子}}// 对比父节点和最小孩子结点// 父亲结点数值 ＞ 最小孩子结点数值if(hp->_a[parent]>hp->_a[minchild]){// 交换父亲与最小孩子结点的数值Swap(&(hp->_a[parent]),&(hp->_a[minchild]));// 旧孩子变新父亲parent=minchild;// 重新假设计算最小孩子下标minchild=parent*2+1;}// 父亲结点数值 ≤ 最小孩子结点数值else{// 已维持小根堆特性,不用再进行调整break;}}}

向下调整算法需要对比两个孩子,向上调整算法只需要对比一个父亲

删除堆顶元素 代码展示 :

// 删除堆顶元素voidHPPop(HP*php){assert(php);// 后续需要对其进行解引用assert(php->size>0);// 保证数组里有东西可以删除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->size>0);returnphp->a[0];}

🐛 判空

返回数组的有效元素个数是否等于0

// 判空boolHPEmpty(HP*php){assert(php);returnphp->size==0;}

---

🐛 堆排序 ( 数组元素 )

若要对数组中数据进行降序排序,建堆时推荐建立小堆

若要对数组中数据进行升序排序,建堆时推荐建立大堆

调整算法里面的比较逻辑决定了建的堆是大堆还是小堆

核心 ----- 先反着建堆,不断找出最值,首尾元素交换,再进行调整

🎣 第一步 ---- 建堆

🥝 第一种建堆方式 — 向上调整建堆

遍历数组中第二个到最后一个元素,每一次遍历都对该元素进行一次向上调整,从而完成建小根堆的过程


🥝 第二种建堆方式 — 向下调整建堆

从倒数的第一个非叶结点开始调

从数组中最后一个元素入手,算出 ta 的父节点下标,从这个下标开始,向下调整一次… 下标每往前移动一个单位,就向下调整一次… 不断循环往复进而完成建堆

🎣 第二步 ---- 排序 ( 假设已经建好小堆 )

交换数组中首尾元素位置,交换后数组中最后一个元素为最小元素

然后再对堆顶元素进行向下调整( 注意此时数组中最后一个元素

已然完成排序,不纳入调整 ) , 进而找出次小的元素

由于数组中最后一个元素已经排好序不纳入调整,所以数组里的有效个数要先 -1 才能进入下一个循环

然后再交换数组中首尾元素位置…

不断循环往复

// 堆排序 --- 降序voidHeapSort(HP*hp){// step1.--- 向下调整建小堆intparent=(hp->size-1-1)/2;for(inti=parent;i>=0;i--){AdjustDown(hp,i);}// step2.--- 排序// 数组里有效元素个数至少2个,交换才有意义while(hp->size>1){// 交换数组中首尾元素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 层共有2¹个结点,最坏情况是这一层的每一个结点都要往下调 h-2 层.共计调了 (h-2)*2¹次
• 第 1 层共有2⁰个结点,最坏情况是这一层的每一个结点都要往下调 h-1 层.共计调了 (h-1)*2⁰次

所以 ,总共的调整次数其实是关于 层高 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)+\dots+2^{h-3}\cdot 2+2^{h-2}\cdot 1 \tag{1}T(h)=20(h−1)+21(h−2)+22(h−3)+23(h−4)+⋯+2h−3⋅2+2h−2⋅1(1)

经典的 等差 * 等比 用错位相减法求解

一般来讲 , 研究二叉树最后结论都要往结点个数上面去靠拢 , 所以接下来研究 节点个数与层高 h 的关系 ,进而将 总调整次数 转化为关于总结点个数的函数

以满二叉树来举例:

• 第 1 层共有 2⁰个结点

• 第 2 层共有 2¹个结点

• 以此类推…

• 第 h-1 层共有 2^h-2个结点

• 第 h 层共有 2^h-1个结点

不妨设总共的结点数为 N

则有 :N = 2 0 + 2 1 + 2 2 + ⋯ + 2 h − 2 + 2 h − 1 N=2^0+2^1+2^2+\dots+2^{h-2}+2^{h-1}N=20+21+22+⋯+2h−2+2h−1

可得 :
N = 2 h − 1 , h = log ⁡ 2 ( N + 1 ) N=2^h-1,\quad h=\log_2(N+1)N=2h−1,h=log2​(N+1)

所以

所以,向下调整法建堆的时间复杂度为 O ( N )

时间复杂度只保留影响最大的那个项

---

💘 分析 step1-2 向上调整法建堆 的时间复杂度

假设完全二叉树的结点个数为 N ,树高为 h

向上调整法建堆,调整是从第二层开始的

• 第 2 层共有 2¹个元素,最坏情况所有元素都要往上调 1 层.共调 1*2¹次
• 第 3 层共有 2²个元素,最坏情况每个元素都熬往上调 2 层.共调 2*2²次
• 以此类推…
• 第 h-1 层共有2^h-2个元素,最坏情况每个元素都要往上调 h-2 层.共调 (h-2)*2^h-2次
• 第 h 层共有 2^h-1个元素,最坏情况每个元素都要往上调 h-1 层.共调 (h-1)*2^h-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⋅1+22⋅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)=−(20+21+22+⋯+2h−1)+2h⋅(h−1)+20

又由 满二叉树层高与结点个数换算公式 :
N = 2 h − 1 , h = log ⁡ 2 ( N + 1 ) N=2^h-1,\quad h=\log_2(N+1)N=2h−1,h=log2​(N+1)

可得 :

T ( N ) = − N + ( N + 1 ) ⋅ ( log ⁡ 2 ( N + 1 ) − 1 ) + 1 T(N) = -N + (N+1)\cdot\big(\log_2(N+1)-1\big) + 1T(N)=−N+(N+1)⋅(log2​(N+1)−1)+1

所以 ,向上调整法建堆的时间复杂度为 O ( N * logN )

所以,在进行建堆时,向下调整算法明显优于向上调整算法

---

💘 分析 step2. 排序 的时间复杂度

从结点最多的最后一层分析

最后一层的结点数量为 2^h-1个

交换数组首尾元素后,最坏情况是要往下调 h-1 层

所以,最后一层的结点最坏情况下,总的调整次数为 2^h-1*(h-1) 次

又由 满二叉树层高与结点个数换算公式 :
N = 2 h − 1 , h = log ⁡ 2 ( N + 1 ) N=2^h-1,\quad h=\log_2(N+1)N=2h−1,h=log2​(N+1)

可知 :

2 h − 1 ( h − 1 ) = 2 log ⁡ 2 ( h + 1 ) − 1 2^{h-1}(h-1) = 2^{\log_2(h+1)-1}2h−1(h−1)=2log2​(h+1)−1

则有 :

所以,最后一层排序的时间复杂度为 N*logN

因为最后一层结点最多,对总的调整次数影响最大,所以这个step2.排序 的时间复杂度就是 O ( N*logN )

---