数据结构和算法

线性表结构

💡 Tips：是最常用且是最简单的一种数据结构。形如：A1、A2、A3….An这样含有有限的数据序列，我们就称之为线性表。

• 数组

   数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。如果你学习过 C 语言，应该对这段定义很熟悉，但是在 PHP 这种动态语言中，因为数组底层是通过散列表（后面我们会介绍这个数据结构）实现的，所以功能异常强大，这段常规的数组定义在 PHP 中并不成立，PHP 的数组可以存储任何类型数据，如果与 Java 对比的话，PHP 数组集成了 Java 的数组、List、Set、Map 于一身，所以写代码的效率比 Java 高了几个量级。

• 链表

  — 单链表
  单链表中有两个节点比较特殊，分别是第一个结点和最后一个结点。我们通常把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址，有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。对单链表而言，理论上来说，插入和删除节点的时间复杂度是 O(1)，查询节点的时间复杂度是 O(n)。
  — 循环链表
  然后还有在单链表的基础上扩展还有循环链表，循环链表和单链表的区别是尾节点指向了头结点，从而首尾相连，有点像贪吃蛇，可用于解决「约瑟夫环」问题，循环链表的结构如图所示：
  
  — 双向链表
  此外，还有比较常见的双向链表，顾名思义，与单链表的区别是双向链表除了有一个指向下一个节点的指针外，还有一个用于指向上一个节点的指针，从而实现通过 O(1) 复杂度找到上一个节点。正是因为这个节点，使得双向链表在插入、删除节点时比单链表更高效，虽然我们前面已经提到单链表插入、删除时间复杂度已经是 O(1) 了，但是这没有考虑还只是针对插入、删除操作本身而言，以删除为例，删除某个节点后，需要将其前驱节点的指针指向被删除节点的下一个节点，这样，我们还需要获取其前驱节点，在单链表中获取前驱节点的时间复杂度是 O(n)，所以综合来看单链表的删除、插入操作时间复杂度也是 O(n)，而双向链表则不然，它有一个指针指向上一个节点，所以其插入和删除时间复杂度才是真正的 O(1)。
  此外，对于有序链表而言，双向链表的查询效率显然也要高于单链表，不过更优的时间复杂度是靠更差的空间复杂度换取的，双向链表始终需要单链表的两倍空间，但是正如我们之前说的，在 Web 应用中，时间效率优先级更高，所以我们通常都是空间换时间来提高性能，Java 的 LinkedHashMap 底层就用到了双向链表。
  双向链表的结构如图所示：
  
  — 双向循环链表
  最后我们要介绍的是结合循环链表和双向链表为一体的双向循环链表：
  

• 栈
  栈又叫堆栈，是限定只能在一端进行插入和删除操作的线性表，并且满足后进先出（LIFO）的特点。我们把允许插入和删除的一端叫做栈顶，另一个端叫做栈底，不含任何数据的栈叫做空栈。
  栈支持通过数组/链表实现，通过数组实现的通常叫做顺序栈，通过链表实现的叫做链栈。

栈的应用场景：
堆栈在日常开发和软件使用中，应用非常广泛，比如我们的浏览器前进、倒退功能，编辑器/IDE 中的撤 销、取消撤销功能，程序代码中的函数调用、递归、四则运算等等，都是基于堆栈这种数据结构来实现的，就连著名的 stackoverflow 网站也是取「栈溢出」，需要求教之意。

• 队列
  队列的特性是先入先出（FIFO），允许插入的一端叫队尾，允许删除的一端叫队头。一张图可以形象的体现队列和栈两者的差别：
  

  常见排序算法

  💡 Tips：最常见的排序算法总结：冒泡排序，插入排序，选择排序，归并排序，快速排序。搭配动态图查看效果更佳：https://visualgo.net/zh/sorting

• 冒泡排序
  实现原理： 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作
  通过图示来直观冒泡排序 4、5、6、3、2、1

冒泡排序性能分析：

1. 时间复杂度： O(n2)
2. 空间复杂度：只涉及相邻元素的交换，是原地排序算法
3. 算法稳定性：元素相等不会交换，是稳定的排序算法
   总结：冒泡排序的算法性能并不理想。但绝对不会出错

• 插入排序(选择中间的位置插入)

  插入排序的原理是：我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
  
  插入排序性能分析:

• 插入排序需要两个嵌套的循环，时间复杂度是O(n2)；

• 没有额外的存储空间，是原地排序算法；
• 不涉及相等元素位置交换，是稳定的排序算法。
• 选择排序(选择最小的)

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。图示如下：

选择排序性能分析:

• 很显然，选择排序的时间复杂度也是 O(n2)
• 由于不涉及额外的存储空间，所以是原地排序；
• 由于涉及非相邻元素的位置交换，所以是不稳定的排序算法。

综上所述在三种排序复杂度相对高的算法中使用优先级 插入排序 > 冒泡排序 > 选择排序

• 归并排序
  所谓归并排序，指的是如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
  归并排序使用了分治思想，分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。说到这里，可能你就能联想起我们之前讲到的一个编程技巧 —— 递归，没错，归并排序就是通过递归来实现的。这个递归的公式是每次都将传入的待排序数组一分为二，直到不能分割，然后将排序后序列合并，最终返回排序后的数组。
  

归并排序性能分析：
归并排序不涉及相等元素位置交换，是稳定的排序算法，时间复杂度是 O(nlogn)，要优于冒泡排序和插入排序的 O(n2)，但是归并排序需要额外的空间存放排序数据，不是原地排序，最多需要和待排序数组同样大小的空间，所以空间复杂度是 O(n)。

• 快速排序(性能相对最好的算法)

实现原理： 归并排序算法虽好，但是不是原地排序算法，需要消耗额外的内存空间，今天我们要介绍的是常规排序里综合排名最高的排序算法：快速排序，江湖人称「快排」。
快排的核心思想是这样的：
如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。


性能分析：
正如我们前面所说的，快速排序是原地排序算法，时间复杂度和归并排序一样，也是 O(nlogn)，这个时间复杂度数据量越大，越优于 O(n2)，但是快速排序也有其缺点，因为涉及到数据的交换，有可能破坏原来相等元素的位置排序，所以是不稳定的排序算法，尽管如此，凭借其良好的时间复杂度表现和空间复杂度的优势，快速排序在工程实践中应用较多，比如 PHP 数组的 sort 函数底层就是基于快速排序来实现的，明天我们就来一起探究下 PHP 底层 sort 函数是如何实现的。

查找算法

• 二分查找实现原理(重点)
  所谓二分查找，针对的是一个有序的数据集合（这点很重要），查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。注意到二分查找针对的必须是已经排序过的有序数组，否则不能使用该算法。图示如下：
  性能分析:

二分查找的时间复杂度是 O(logn)。这是一个非常恐怖的数量级，有时候甚至比 O(1) 还要高效，比如我们要在开头提到的 40 亿个数字中查找某一个元素，也只需要32次（2 的 32 次方是 40 亿数量级），这真的是非常高效了，正因如此二分查找在线性表结构中的应用非常广泛。
但是使用二分查找需要注意一个前提，那就是针对有序数组，换言之，二分查找适用于变动不是很频繁的静态序列集，如果序列集变动很频繁，经常进行插入删除操作，那么就要不断维护这个序列集的排序，这个成本也很高，因此，这种情况下就不适用二分查找了，比如我们的数据库查询，增删改查很频繁，显然不是通过二分查找来进行查询的，后面我们会讨论，如何针对动态变化的序列集进行查询操作。

散列表

散列表（HashTable，也叫哈希表），是根据键（Key）直接访问在内存存储位置的数据结构。
其实现原理是：通过散列函数（也叫哈希函数）将元素的键映射为数组下标（转化后的值叫做散列值或哈希值），然后在对应下标位置存储记录值。当我们按照键值查询元素时，就是用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据：

散列函数设计：
首先我们大家常用的MD5函数就是一个散列函数，这样就很好理解了

• 直接定址法：即 f(key) = a*key + b，f 表示散列函数，a、b 是常量，key 是键值
• 数字分析法：即对数字做左移、右移、反转等操作获取散列值
• 除数留余法：即 f(key) = key % p，p 表示容器数量，这种方式通常用在将数据存放到指定容器中，如何决定哪个数据放到哪个容器，比如分表后插入数据如何处理（此时 p 表示拆分后数据表的数量），分布式 Redis 如何存放数据（此时 p 表示几台 Redis 服务器）
• 随机数法：即 f(key) = random(key)，比如负载均衡的 random 机制

以上只是一些比较场景的散列函数设计思路，还有很多其他的设计方法，这里就不一一列举了。
散列冲突处理:
设计再好的散列函数也不能完全避免散列冲突，我们只能优化自己的实现让散列冲突尽可能少出现罢了，如果出现了散列冲突，该如何处理呢？下面给出一些思路：

• 开放寻址法：该方法又可以细分为三种 —— 线性寻址、二次探测、随机探测。线性寻址表示出现散列冲突之后，就去寻找下一个空的散列地址；线性寻址步长是1，二次探测步长是线性寻址步长的2次方，其它逻辑一样；同理，随机探测每次步长随机。不管哪种探测方法，散列表中空闲位置不多的时候，散列冲突的概率就会提高，为了保证操作效率，我们会尽可能保证散列表中有一定比例的空闲槽位，我们用装载因子来表示空位的多少，装载因子=填入元素/散列表长度，装载因子越大，表明空闲位置越少，冲突越多，散列表性能降低。
• 再散列函数法：发生散列冲突后，换一个散列函数计算散列值
• 链地址法：发生散列冲突后，将对应数据链接到该散列值映射的上一个值之后，即将散列值相同的元素放到相同槽位对应的链表中。链地址法即使在散列冲突很多的情况下，也可以保证将所有数据存储到散列表中，但是也引入了遍历单链表带来性能损耗。

介绍完以上内容之后，想必你对如何打造工业级散列表已经心中有数。主要考虑因素包含以下几个方面：

• 散列函数设置合理，不能太过复杂，成为性能瓶颈；
• 设置装载因子阈值，支持动态扩容，装载因子阈值设置要充分权衡时间、空间复杂度；
• 如果一次性扩容耗时长，可采取分批扩容的策略，达到阈值后只申请空间，不搬移数据，以后每插入一条数据，搬移一个旧数据，最后逐步完成搬移，期间为了兼容新老散列表查询，可以先查新表，再查老表；
• 散列冲突解决办法：开放寻址法在数据量较小、装载因子小的时候（小于1）选用；链表法可以容忍装载因子大于1，适合存储大对象、大数据量的散列表，且更加灵活，支持更多优化策略。

哈希算法及其应用场景：
哈希算法的一般特征：

• 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向算法，不可逆）；
• 对输入数据非常敏感，哪怕原始数据只修改了一个比特，最后得到的哈希值也大不相同；
• 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
• 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值

1、场景一：安全加密
我们日常用户密码加密通常使用的都是 md5、sha 等哈希函数，因为不可逆，而且微小的区别加密之后的结果差距很大，所以安全性更好。
2、场景二：唯一标识
比如我们的 URL 字段或者图片字段要求不能重复，这个时候就可以通过对相应字段值做 md5 处理，将数据统一为 32 位长度从数据库索引构建和查询角度效果更好，此外，还可以对文件之类的二进制数据做 md5 处理，作为唯一标识，这样判定重复文件的时候更快捷。
3、场景三：数据校验
比如我们从网上下载的很多文件（尤其是 P2P 站点资源），都会包含一个 MD5 值，用于校验下载数据的完整性，避免数据在中途被劫持篡改。
4、场景五：散列函数
前面我们已经提到，PHP 中的 md5、sha1、hash 等函数都是基于哈希算法计算散列值。
5、场景五：负载均衡
对于同一个客户端上的请求，尤其是已登录用户的请求，我们需要将其会话请求都路由到同一台机器，以保证数据的一致性，这可以借助哈希算法来实现，通过用户 ID 尾号对总机器数取模（取多少位可以根据机器数定），将结果值作为机器编号。
6、场景六：分布式缓存
分布式缓存和其他机器或数据库的分布式不一样，因为每台机器存放的缓存数据不一致，每当缓存机器扩容时，需要对缓存存放机器进行重新索引（或者部分重新索引），这里应用到的也是哈希算法的思想。后面我们介绍 Redis 系列的时候会系统阐述这一块。

字符串匹配

• 字符串匹配算法之BF算法
  首先理解BF BF 是 Brute Force 的缩写，中文译作暴力匹配算法，也叫朴素匹配算法。BF 算法的原理很简单，在继续介绍之前，我们先引入两个术语：主串和模式串。简单来说，我们要在字符串 A 中查找子串 B，那么 A 就是主串，B 就是模式串。
  作为最简单、最暴力的字符串匹配算法，BF 算法的思想可以用一句话来概括，那就是，如果主串长度为 n，模式串长度为 m，我们在主串中检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。图示如下：
  
  结合上图，具体来说，就是每次拿模式串和主串对齐，然后从左到右依次比较每个字符，如果出现不相等，则把模式串往后移一个位置，再次重复上述步骤，直到模式串每个字符与对应主串位置字符都相等，则返回主串对应下标，表示找到，否则返回 -1，表示没找到。

这个算法很好理解，因为这就是我们正常都能想到的暴力匹配，BF 算法的时间复杂度最差是 O(nm)，意味着要模式串要移到主串 n-m 的位置上，并且模式串每个字符都要与子串比较。
尽管 BF 算法复杂度看起来很高，但是在日常开发中，如果主串和模式串规模不大的话，该算法依然比较常用，因为足够简单，实现起来容易，不容易出错。另外，在规模不大的情况下，开销也可以接受，毕竟 O(nm) 是最差的表现，大部分时候，执行效率比这个都要高。
但是对于对时间要求比较敏感，或者需要高频匹配，数据规模较大的情况下，比如编辑器中的匹配功能、敏感词匹配系统等，BF 算法就不适用了，后面我们将介绍更高级的字符串匹配算法来处理这些场景需求。
总结：BF只适用数据规模较小的场景

• 字符串匹配算法之KMP算法

核心思想：假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况，从而避免 BF 算法这种暴力匹配，提高算法性能。下面我们来探讨下这个规律如何找到。
参考下面个主串和模式串的匹配，当模式串移动到当前位置，比对到最后一个字符 D 时，发现与主串不匹配，如果按照 BF 算法，就是把模式串往后移一位，再逐个比较，这样做固然可以，但是效率很差：

一个基本事实是，当 D 与主串不匹配时，我们已知前面的主串序列是 ABCDA，如果把模式串往后移一位肯定和主串不匹配，我们可不可以直接把模式串移到下一个可能和 A 匹配的主串位置？
实际上，KMP 算法正是基于这一理念，设法利用这个已知信息，不把模式串移到已经比较过的位置，继续把它向后移，这样综合下来就极大提高了搜索匹配效率。
怎么找到这个规律，确定把模式串往后移多少位呢？在模式串和主串匹配的过程中，我们把不能匹配的那个字符仍然叫作「坏字符」，把已经匹配的那段字符串叫作「好前缀」：

在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的下标位置，然后将模式串后移到该位置即可。
这里，我们要解释几个概念：

• 后缀子串：以某个字符串最后一个字符为尾字符的子串（不包含字符串自身），比如上面的 ababa，后缀子串为 baba、aba、ba、a；
• 前缀子串：以某个字符串第一个字符为首字符的子串（不包含字符串自身），还是以 ababa 为例，前缀子串为 a、aba、abab；
• 最长可匹配后缀子串：后缀子串与前缀子串最长可匹配子串，也可叫做共有子串，以 ababa 为例，自然是 aba 了，长度为 3；
• 最长可匹配前缀子串：与上面定义相对，即前缀子串与后缀子串最长可匹配子串。最长可匹配前缀子串和最长可匹配后缀子串肯定是一样的。

假设坏字符所在位置是 j，最长可匹配后缀子串长度为 k，则模式串需要后移的位数为 j-k。每当我们遇到坏字符，就将模式串后移 j-k 位，直到模式串与对应主串字符完全匹配；如果移到最后还是不匹配，则返回 -1。这就是 KMP 算法的核心思想。

KMP 算法的实现
了解了核心思想，接下来，就可以考虑如何实现 KMP 算法了，实现 KMP 算法最核心的部分是构建一个用来存储模式串中每个前缀子串（这些前缀都有可能是好前缀）最长可匹配前缀子串的结尾字符下标数组，我们把这个数组叫做 next 数组，对于上面 ababacd 这个模式串而言，对应的 next 数组如下：

其中，数组的下标是前缀子串结尾字符下标，数组的值是这个前缀的最长可匹配前缀子串的结尾字符下标。
有了这个 next 数组，我们就可以实现 KMP 匹配算法的核心代码了：1
// KMP 算法 PHP 实现代码，$a 表示主串，$n 表示主串长度，$b 表示模式串，$m 表示模式串长度

function kmp($a, $n, $b, $m)
{
    $next = generateNexts($b, $m);   // 生成 next 数组
    $j = 0;
    for ($i = 0; $i < $n; $i++) {  // 遍历主串
        while ($j > 0 && $a[$i] != $b[$j]) {  
            // 如果主串字符和模式串字符不相等，
            // 更新模式串坏字符下标位置为好前缀最长可匹配前缀子串尾字符下标+1
            // 然后从这个位置重新开始与主串匹配
            // 相当于前面提到的把模式串向后移动 j - k 位
            $j = $next[$j - 1] + 1;
        }
        if ($a[$i] == $b[$j]) {
            $j++;
        }
        if ($j == $m) {
            return $n - $m + 1;  // 全部相等，找到匹配位置
        }
    }
    return -1;
}

接下来就是如何生成 next 数组了，这一步是最难的，我们现在可以参考上面 next 数组生成原理通过循环比对前缀子串和后缀子串的方式去理解，毕竟我们在实际开发中不太可能自己去实现 KMP 算法，了解原理即可，以后讲到动态规划，会用动态规划来实现它。这里就不再深入探究了。

二叉树

在继续介绍其它字符串匹配算法 Trie 树之前，我们先来讲讲树这种数据结构，因为 Trie 树也是一棵树。树比前面讲的数据结构（数组、链表、栈、队列、散列表等）都要复杂，我们需要花大量篇幅来介绍其概念、特性、遍历、存储及使用。

树的相关概念

树这种数据结构模拟了自然界中树的概念，自然界中的树有根、叶子、枝干，数据结构中的树也是如此，只不过是倒过来的：

其中的每个元素叫做节点。树的顶点（没有父元素的节点）叫根节点，如 E；每个分支的末端节点（没有子元素的节点）叫叶子节点，如 G、H、I、J、K、L；用来连接相邻节点之间的关系叫父子关系，比如 E 是 A、F 的父节点，A、F 是 E 的子节点；具有同一个父节点的多个子节点叫做兄弟节点，比如 A、F 是兄弟节点。
节点拥有的子节点数目叫做节点的度，显然，叶子节点的度为 0，树的度是树内各节点度的最大值。
除此之外，树还有高度、深度和层的概念：


注：其实线性表也可以看作一种特殊的树，只不过所有节点都在一个分支上，第一个元素是根节点，最后一个元素是子节点，没有兄弟节点。层数就是线性表的长度。
另外，也有些地方将二叉树的深度定义为结点的最大层次数，比如《大话数据结构》就是这样定义的，这个问题不大，完全就是个定义而已：

多个互不相交的树可以构成森林。

二叉树的定义

二叉树是我们平时遇到的最常见的树结构，它是一种特殊的树，顾名思义，就是每个节点最多有两个「分叉」，即两个子节点，分别是左子节点和右子节点，不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子结点，有的节点只有右子节点。比如下面这些都是二叉树：

根据左右子节点的饱和度，我们又从二叉树中提取出两种特殊的二叉树 —— 满二叉树和完全二叉树。满二叉树即所有分支节点都有左右子节点，并且所有叶子节点都在同一层上，如上面的图2便是满二叉树。完全二叉树要复杂一些，深度为 k 有 n 个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度 k 的满二叉树，序号为 1 到 n 的节点一对一对应时，称为完全二叉树，比如上面的图3就是完全二叉树。

其他的参考理解方式

• 每个结点的度（结点拥有的子树数目）不超过2的树叫做二叉树
• 二叉树的深度
• 结点的最大层次数称为树的深度或高度
• 满二叉树
• 指深度为k且有2k−1个结点的二叉树，即所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。
• 下图中深度为4，24−1=15个结点，且所有叶子都在第四层上。
• 完全二叉树
• 一颗深度为k的二叉树，k层的结点都是连续靠左并不可隔开的，并且1～k-1层的结点也组成了一棵满二叉树，这样的二叉树，我们称为完全二叉树。
• 完全二叉树的线性存储
• 出于简便起见,完全二叉树通常采用数组进行线性存储

  二叉树的特性

  在讨论二叉树的创建和存储之前，我们先来总结下二叉树的一些特性，以便后续用到（这里二叉树数的深度定义采用的最大层次数，如果从 0 开始计算的话，可以自行推演一下）：
  性质1：
  在第 i 层最多有 2i-1 个节点。
  性质2：
  深度为 k 的二叉树最多有 2k-1 个节点。
  性质3：
  对于任何一个二叉树，叶子节点数为 n0，度为 2 的节点数为 n2，则 n0 = n2+1。
  性质4：
  性质5：
  

  二叉树的存储

  
  前面我们聊到树和二叉树的定义和特性，树这种结构不能简单通过线性表的前后关系来存储，在线性表中，一个节点只有至多一个前驱节点和至多一个后驱节点，树则不然，一个节点可能有多个后驱节点，这个时候，我们需要通过更加复杂的结构才能存储树。二叉树是一种特殊的树，比多叉树要简单，因为特定节点至多只有两个节点，这就极大简化了相应的数据结构，使得通过线性表就可以实现二叉树的存储。我们后面基本只讨论二叉树，下面我们通过数组和链表来演示如何存储二叉树。
  通过数组存储二叉树
  对于特定的二叉树而言，比如满二叉树、完全二叉树，它们的节点之间是有一定关联关系的，以下面这棵完全二叉树为例：
  
  我们按照从上到下，从左到右对所有节点编号，可以看到，下一层的左右子节点和对应父节点序号存在某种数学关系，如果父节点的序号是 i，其对应左子节点位于 2i 的位置上，对应右子节点位于 2i + 1 的位置上，我们可以参照这个规则将上述完全二叉树存储到数组中：
  
  注意我们的下标从 1 开始（根节点），索引为 0 的下标舍弃，浪费这个空间，以方便计算。这样，我们就可以从根节点开始，依次将所有节点元素存放到数组中，并且可以根据节点间的数学关系很方便地遍历整棵树。此外，由于完全二叉树的特殊性，除了第一个元素之外，该数组不存在任何空间的浪费。由于满二叉树是完全二叉树的子集，所以也可以通过这种方式来存储。
  那么其它二叉树呢？当然也可以按照这种思路来做，我们把不存在的节点补全，比如假设上述序号为 4、6、8、9 的元素不存在：
  
  可以看到，我们将不存在的元素补上，只是对应位置值为 null，缺失的节点越多，数组的「空洞」也就越多，如果是极端情况，比如二叉树只包含 1、3、7 三个元素，那么数组中将会存在大量的「空洞」，浪费大量的空间，而且也会影响性能。
  综上，数组适合满二叉树、完全二叉树这些特殊二叉树的存储，一些比较稠密的二叉树也可以用数组，如果二叉树比较稀疏就不适合用数组了，我们可以通过链表来存储它们。

通过链表存储二叉树
理论上来说，链表适用于所有的二叉树存储，只不过这里我们需要对线性表中的链表进行扩展，因为二叉树特定节点最多有两个子节点，所有我们在链表结点上设置两个指针域，分别指向左右子节点，所以这种链表结构又被称作二叉链表。我们可以通过一个类表示二叉链表的结点：

class Node
{
    public $data;
    public $left = null;
    public $right = null;
    public function __construct($data)
    {
        $this->data = $data;
    }
}

总之：不管是什么样结构的二叉树，用链表来存储都不会存在空间的浪费。只不过针对不同的二叉树类型以及权衡完效率以后使用合适的存储方式。有多种方式可以遍历二叉树，如果限制从左到右的习惯方式，主要分为三种：前序遍历、中序遍历和后序遍历。下面我们简单介绍这几种遍历方式及对应实现算法，所谓的前序、中序和后序都是以根节点作为参照系。

二叉树的遍历

前序遍历 如果二叉树为空，则返回空，否则从根节点开始，先遍历左子树，再遍历右子树：

中序遍历： 同样，如果是空树，返回空，否则从左子树最左侧的节点开始，然后从左到右依次遍历左子树，真正的根节点，最后是右子树（依然是从最左侧节点开始从左到右的顺序遍历）：

后序遍历： 如果是空树，返回空，否则还是从左子树最左侧的节点开始，先遍历完叶子节点，再遍历父节点，遍历完左子树后，直接从右子树最左侧节点开始，按照和左子树同样的顺序遍历完右子树，最后访问根节点：

如果是空树，返回空，否则还是从左子树最左侧的节点开始，先遍历完叶子节点，再遍历父节点，遍历完左子树后，直接从右子树最左侧节点开始，按照和左子树同样的顺序遍历完右子树，最后访问根节点：

<?php
// 二叉链表节点
class Node
{
    public $data;
    public $left = null;
    public $right = null;
    public function __construct($data)
    {
        $this->data = $data;
    }
}
/**
 * 前序遍历
 * @param Node $tree
 */
function preOrderTraverse($tree)
{
    if ($tree == null) {
        return;
    }
    printf("%s\n", $tree->data);
    preOrderTraverse($tree->left);
    preOrderTraverse($tree->right);
}
/**
 * 中序遍历
 * @param Node $tree
 */
function midOrderTraverse($tree)
{
    if ($tree == null) {
        return;
    }
    midOrderTraverse($tree->left);
    printf("%s\n", $tree->data);
    midOrderTraverse($tree->right);
}
/**
 * 后序遍历
 * @param Node $tree
 */
function postOrderTraverse($tree)
{
    if ($tree == null) {
        return;
    }
    postOrderTraverse($tree->left);
    postOrderTraverse($tree->right);
    printf("%s\n", $tree->data);
}
$node1 = new Node('A');
$node2 = new Node('B');
$node3 = new Node('C');
$node1->left = $node2;
$node1->right = $node3;
preOrderTraverse($node1);
print "=======\n";
midOrderTraverse($node1);
print "=======\n";
postOrderTraverse($node1);

二叉排序数

1. 什么是二叉排序树？
   二叉排序树是一种特殊的二叉树，我们重点关注「排序」二字，二叉排序树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值，所以这么看来，二叉排序树是天然有序的，如果按照昨天讲的中序遍历，得到将是一个从小到大的有序数据集。但是构造二叉排序树的目的，并不是为了排序，而是为了提高查找、插入和删除的速度。不管怎么说，在一个有序数据集上查找数据肯定比无序数据集要快，同时二叉排序树这种非线性结构，也非常有利于插入和删除的实现。

2. 为什么要引入二叉排序数
   我们已经知道很多的数据结构。比如数组、链表、散列表等，数组查找性能高，但是插入、删除性能差，链表插入、删除性能高，但查找性能差，在不考虑散列冲突的话，散列表的插入、删除、查找性能都很高，但是前提是没有散列冲突，此外，散列表存储的数据是无序的，散列表的扩容非常麻烦，涉及到散列冲突时，性能不稳定，另外，散列表用起来爽，构造起来可不简单，要考虑散列函数的设计、哈希冲突的解决、扩容缩容等一系列问题，有没有一种插入、删除、查找性能都不错，构建起来也不是很复杂，性能还很稳定的数据结构呢？这就是我们今天要介绍的数据结构 —— 二叉排序树。

3. 代码实现

<?php
class Node {
    public  $root;
    public $left = null;
    public $right = null;
    //初始化
    public function __construct($root)
    {
        $this->root = $root;
    }
    /**
     * @return mixed
     * 前序遍历
     */
    public function getRoot($tree)
    {
        if ($tree == null) {
            return;
        }
        printf("%s\n",$tree->root);
        $this->getRoot($tree->left);
        $this->getRoot($tree->right);
    }
    /**
     * @return null
     * 中序遍历
     */
    public function getLeft($tree)
    {
        if ($tree == null) {
            return;
        }
        $this->getRoot($tree->left);
        printf("%s\n",$tree->root);
        $this->getRoot($tree->right);
    }
    /**
     * @param null $right
     * 后序遍历
     */
    public function getRight($tree)
    {
        if ($tree == null) {
            return;
        }
        $this->getRoot($tree->left);
        $this->getRoot($tree->right);
        printf("%s\n",$tree->root);
    }
}
$node1 = new Node('a');
$node2 = new Node('b');
$node3 = new Node('c');
$node1 ->left = $node2;
$node1->right = $node3;
$node1->getRoot($node1);
print "===========\n";
$node1->getLeft($node1);
print "===========\n";
$node1->getRight($node1);
print "===========\n";

<?php
//定义二叉树的类
class Node {
    public $data;
    public $left = null;
    public $right = null;
    public function __construct($data)
    {
        $this->data = $data;
    }
}
/***
 * 二叉树的增和查询方法
 */
class BinarySortTree {
    //获取当前树
    private $tree;
    public function getTree()
    {
        return $this->tree;
    }
    //插入元素
    /**
     * @param mixed $tree
     */
    public function insertTree($data)
    {
        //如果树不存在节点就为跟节点
        if(!$this->tree) {
            $this->tree = new Node($data);
            return;
        }
        $p = $this->tree;
        while ($p) {
            //如果小于就为左节点
            if ($data < $p->data){
                if (!$p->left){
                    $p->left = new Node($data);
                    return;
                }
                $p = $p ->left;
            }elseif ($data > $p -> data) {
                if (!$p->right){
                    $p->right = new Node($data);
                    return;
                }
                $p = $p->right;
            }
        }
    }
    /***
     * 二叉树查找
     */
    public function findTreeNode($data)
    {
        $p = $this->tree;
        while ($p) {
             if ($data < $p->data){
                 $p = $p ->left;
             }elseif ($data > $p->data){
                 $p = $p ->right;
             } else{
                 return $p;
             }
        }
    }
}
$tree = new BinarySortTree();
$tree->insertTree(5);
$tree->insertTree(8);
$tree->insertTree(4);
$tree->insertTree(1);
$tree->insertTree(9);
$tree->insertTree(2);
$tree->insertTree(7);
$tempData = $tree->getTree();
$findData = $tree->findTreeNode(4);
print_r($findData);

关于二叉树的总结：
不论是插入、删除、还是查找，二叉排序树的时间复杂度都等于二叉树的高度，最好的情况当然是满二叉树或完全二叉树，此时根据完全二叉树的特性，时间复杂度是 O(logn)，性能相当好，最差的情况是二叉排序树退化为线性表（斜树），此时的时间复杂度是 O(n)，所以二叉排序树的形状也很重要，不同的形状会影响最终的操作性能，所以下一篇我们将讨论如何实现平衡的二叉排序树 —— 平衡二叉树（AVL）。
如果出现斜树等会很影响效率

平衡二叉树

平衡二叉树的英文名是 Self-Balancing Binary Search Tree 或者 Height-Balancing Binary Search Tree，译作自平衡的二叉查找树，(你首先得是一个排序二叉树) 或者高度平衡的二叉查找树，二叉查找树和二叉排序树是一个意思，只是叫法不同，简称平衡二叉树，也叫 AVL 树（平衡二叉树作者的名字首字母），所以平衡二叉树首先是二叉排序树，并且这个二叉排序树是左右高度平衡的，这么讲有点抽象，具体来说，平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1，这个高度（深度）差的值叫做平衡因子 BF，也就是说 BF 的值不能大于1，否则就不是平衡二叉树。

平衡二叉树
不是平衡二叉树，因为58节点的平衡因子为3
不是平衡二叉树。因为首先不是一个排序二叉树
平衡二叉树的实现原理

平衡二叉树的基本实现思路，是在构建二叉排序树的时候，每插入一个节点，都要检查这个节点的插入是否破坏了原有的平衡性，如果是的话，则找出最小不平衡子树，在保证整体二叉排序树的前提下，通过左旋或者右旋的方式将其调整为平衡子树。从而动态维护这棵平衡二叉树。

最小不平衡数

距离插入节点最近的，且平衡因子绝对值大于 1 的节点为根的子树，叫做最小不平衡子树：

比如上图中以存储元素 58 的节点为根的子树叫做最小不平衡子树。
左旋和右旋
所谓左旋和右旋指的是最小不平衡子树旋转的方向。
如果平衡因子小于 -1，即右子树高度值比较大，则需要左旋：

反之，如果平衡因子大于1，即左子树高度值比较大，则需要右旋：

平衡二叉树的构建实现

实例演示
在开始之前，我们先通过一个对比来加强理解，在没有介绍平衡二叉树之前，你可能会构造出这样的一棵二叉树：

虽然这也是一棵二叉排序树，但是层数达到 8，显然可以通过平衡二叉树来降低层数，提高性能，如果把它转化为平衡二叉树，会是这个样子：

层数降低了一半，变成了 4 层，显然性能要比之前要高。那么这个平衡二叉树是怎么构建的呢？假设插入节点的顺序是{3,2,1,4,5,6,7,10,9,8}，两个节点之前不用考虑，我们从第三个节点开始分析：

插入第三个节点 1 时，左子树高度是 2，右子树高度是 0，高度差的绝对值是 2，不符合平衡二叉树的要求，需要把以 3 为根节点的子树进行右旋，到右图那个样子，左右子树高度差为 0，符合平衡二叉树要求，完成调整。同理，插入第四个节点 4 的时候，左右子树高度为 -1，符合平衡二叉树要求，继续插入第五个节点，此时又不符合平衡二叉树的要求了，这个时候右子树比较高，需要左旋：

旋转的时候以最小不平衡子树为单位，此时最小的不平衡子树是 3、4、5 节点构成的子树，我们以 4 为中心进行左旋，将树结构调整为右图所示的样子，满足了平衡二叉树的要求，停止调整。注意到我们每次新增节点的时候，会调整以每个节点为根节点的左右子树的高度差，然后从最小子树开始进行调整，直到以每个节点为根节点的子树符合平衡二叉树的要求，这样整棵树就符合平衡二叉树的要求了。
继续增加节点，当插入节点 6 时，发现根节点 2 上维护的高度差值为 -2，又不满足平衡二叉树了，这个时候，需要以 2 为中心对树进行左旋，最终调整为右图所示的结构满足平衡二叉树要求（右子树中旋转到根节点的节点对应子树需要移到旋转后二叉树的左子树中）：

继续增加节点 7，此时以 5 为根节点的最小子树不满足平衡二叉树的要求了，需要左旋：

继续增加节点 10，满足平衡二叉树要求，再插入节点 9，又不满足了：

这个时候，情况有点微妙，不像我们之前旋转的时候时候处理情况都比较简单，单纯左转满足不了需求，需要先将以 10 作为根节点的子树做一次右转，再将以 7 为根节点的子树做一次左转，让这棵不平衡子树转化为平衡子树：

这样整棵二叉树就满足平衡二叉树的要求了：

最后，我们插入节点 8，此时情况和刚才类似，这个时候，我们以 9 为根节点对子树进行右旋，再以 6 为根节点对子树进行左旋，最终达到平衡状态：

总结一下，大体的思路是平衡因子 BF 的值大于 1 时，右旋，小于 -1 时左旋，如果最小不平衡子树的 BF 值和其子树的 BF 值符号相反时，需要先将子树进行旋转使两者 BF 值符号相同，再旋转最小不平衡子树。我们将单纯的左旋、右旋叫做单旋处理，将需要两次旋转处理的操作叫做双旋处理。
算法复杂度：二叉排序树的插入、删除、查找时提到，最理想的情况下，时间复杂度是 O(logn)，而平衡二叉树就是这种理想情况，虽然平衡二叉树性能是最好的，也是最稳定的，但是这套算法实现起来比较复杂，每次插入节点和删除节点都需要判断剩下节点构成的二叉排序树是否满足平衡二叉树的要求，如果不满足需要做相应的左旋右旋处理，维护成本高，因此，在工程实践上，我们更多时候使用的是红黑树这种二叉排序树，它是一种不严格的平衡二叉树，实现起来更加简单，性能也接近严格的平衡二叉树

红黑树的特性和算法复杂度

为什么会出现红黑树？ 因为平衡二叉树虽然在增删改查方面性能都很好，但在删除和插入节点的维护成本比较高
红黑树的定义： 红黑树（Red-Black Tree）是每个节点都带有颜色属性的二叉排序（查找）树，具备以下的特征

• 节点是红色或黑色；
• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

下面是一个典型的红黑树示例：

这些约束保证了红黑树的关键特性：从根节点到叶子节点的最长的可能路径不多于最短的可能路径长度的两倍（每条路径红黑相间，且黑色节点数目相同，所以最短的路径上是两个黑色节点，相应的，此时最长路径节点一定是黑-红-黑-红，正好是其两倍），从而保证红黑树无论怎么插入、删除节点大致上也是平衡的。

红黑树的算法复杂度

我们上面提到由于红黑树的特性，可以确保即使在最差情况下，红黑树也是大致平衡的，下面我们来简单推导下红黑树的时间复杂度。
前面我们讲二叉排序树的时候说到二叉排序树的时间复杂度和树的高度成正比，红黑树是红黑相间的，我们可以先把红色的节点去掉，剩下的黑色节点就可能变成四叉树了，比如我们上面示例的那个红黑树。由于红黑树每条路径上黑色节点相同，所以可以继续把这个四叉树转化为完全二叉树，假设黑色节点的数量为 m，这样，这棵树的时间复杂度就是 O(logm) 了；然后我们把红色节点塞回来，红色节点的总数目肯定是小于等于黑色节点的，我们不妨假设等于黑色节点，这样，树的高度就增加一倍，对应的时间复杂度就是 2O(logm) 了，m≈n/2，由于在计算时间复杂度的时候，常量可以舍弃，所以红黑树的时间复杂度也是 O(logn)。虽然这里面都是估算的，但是由于前面提到的红黑树的特性约束，数量级上是没问题的。

为什么工程上大多使用红黑树

红黑树维护成本比平衡二叉树低，性能上也能大致做到 O(logn)，且比较稳定，可以应付最差的情况。

红黑树的动态平衡实现原理分析

插入节点

红黑树规定，插入的节点必须是红色的。而且，二叉排序（查找）树中新插入的节点都是放在叶子节点上。首先，我们来看两种最简单的情况：

• 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
• 如果插入的节点是根节点，那我们直接把它设置为黑色就可以了。

除此之外，其他情况都会违背红黑树的特性，所以我们需要进行动态调整，与平衡二叉树不同，调整的过程除了左右旋转之外，还涉及到节点颜色的调整。
新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况。我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。
有了前面平衡二叉树的铺垫，相信理解起来红黑树的构建过程将会更加轻松。为了方便表述，我们把正在处理的节点叫关注节点。
CASE 1：如果关注节点是 a（待插入节点），它的叔叔节点（父亲的兄弟节点，从二叉排序树的角度来说叫伯伯节点更合适？） d 是红色，我们就依次执行下面的操作：

• 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
• 将关注节点 a 的祖父节点 c 的颜色设置成红色；
• 关注节点变成 a 的祖父节点 c；
• 跳到下面的 CASE 2 或者 CASE 3 继续处理。

CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点，我们就依次执行下面的操作：

• 关注节点变成节点 a 的父节点 b；
• 围绕新的关注节点 b 左旋；
• 跳到 CASE 3。

CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点，我们就依次执行下面的操作：

• 围绕关注节点 a 的祖父节点 c 右旋；
• 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
• 调整结束，至此就构造出来一棵红黑树。

学院君注：在看上面三个 CASE 的时候要动态的去看，从 CASE 1 跳到 CASE 2 或 CASE 3，或者从 CASE 2 跳到 CASE 3，或者从 CASE 3 开始，不要分割开来。如果从 CASE 1 跳到到 CASE 2 或 CASE 3，后两者的关注节点 a 就是 CASE 1 中最终的关注节点 c。

删除节点

删除节点的平衡调整更加复杂，可以分为两步，第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二步是针对关注节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。

1、针对删除节点的初步调整

这里需要注意一下，红黑树的定义中「只包含红色节点和黑色节点」，经过初步调整之后，为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色，「红-黑」或者「黑-黑」。如果一个节点被标记为了「黑-黑」，那在计算黑色节点个数的时候，要算成两个黑色节点。
CASE 1：如果要删除的节点是 a，它只有一个子节点 b，那我们就依次进行下面的操作：

• 删除节点 a，并且把节点 b 替换到节点 a 的位置，这一部分操作跟普通的二叉查找树的删除操作一样；
• 节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义。这种情况下，我们把节点 b 改为黑色；
• 调整结束，不需要进行二次调整。

CASE 2：如果要删除的节点 a 有两个非空子节点，并且它的后继节点就是节点 a 的右子节点 c

• 如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树（否则就不是后继节点了）。我们把节点 a 删除，并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异；
• 然后把节点 c 的颜色设置为跟节点 a 相同的颜色；
• 如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了「红-黑」或者「黑-黑」；
• 这个时候，关注节点变成了节点 d，第二步的调整操作就会针对关注节点来做。

CASE 3：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是右子节点，我们就依次进行下面的操作：

• 找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 CASE 1；
• 将节点 a 替换成后继节点 d；
• 把节点 d 的颜色设置为跟节点 a 相同的颜色；
• 如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了「红-黑」或者「黑-黑」；
• 这个时候，关注节点变成了节点 c，第二步的调整操作就会针对关注节点来做。

2、针对关注节点的二次调整

经过初步调整之后，关注节点变成了「红-黑」或者「黑-黑」节点。针对这个关注节点，我们再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。
CASE 1：如果关注节点是 a，它的兄弟节点 c 是红色的

• 围绕关注节点 a 的父节点 b 左旋；
• 关注节点 a 的父节点 b 和祖父节点 c 交换颜色；
• 关注节点不变；
• 继续从四种情况中选择适合的规则来调整。

CASE 2：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的

• 将关注节点 a 的兄弟节点 c 的颜色变成红色；
• 从关注节点 a 中去掉一个黑色，这个时候节点 a 就是单纯的红色或者黑色；
• 给关注节点 a 的父节点 b 添加一个黑色，这个时候节点 b 就变成了「红-黑」或者「黑-黑」；
• 关注节点从 a 变成其父节点 b；
• 继续从四种情况中选择符合的规则来调整。

CASE 3：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色，我们就依次进行下面的操作：

• 围绕关注节点 a 的兄弟节点 c 右旋；
• 节点 c 和节点 d 交换颜色；
• 关注节点不变；
• 跳转到 CASE 4，继续调整。

CASE 4：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的，我们就依次进行下面的操作：

• 围绕关注节点 a 的父节点 b 左旋；
• 将关注节点 a 的兄弟节点 c 的颜色，跟关注节点 a 的父节点 b 设置成相同的颜色；
• 将关注节点 a 的父节点 b 的颜色设置为黑色；
• 从关注节点 a 中去掉一个黑色，节点 a 就变成了单纯的红色或者黑色；
• 将关注节点 a 的叔叔节点 e 设置为黑色；
• 调整结束。

为什么叶子节点都是黑色的空节点

你可能会好奇，为什么叶子节点都是黑色的空节点，其实这就是为了红黑树实现起来更方便。只要满足这一条要求，那在任何时刻，红黑树的平衡操作都可以归结为我们刚刚讲的那几种情况。
不要担心这么做会浪费存储空间，因为其实只要一个空节点就好了：

注：以上红黑树的动态平衡过程主要参考了极客时间王争的算法专栏相应教程。关于红黑树的实现原理，了解其大致实现过程就好了，如果觉得复杂，看不懂，也没啥关系，毕竟基本上不会遇到手动实现红黑树的场景。

解决 TopK 问题 （二叉树典型应用）

• 实现 TopK 排行榜：日常开发中，经常遇到类似求销售额 Top10，浏览数 Top10，点赞数 Top10 之类的需求，也可以通过堆排序来实现，原理就是维护一个大小为 K 的小顶堆，有新数据进入后，如果值比堆顶元素大，则删除堆顶元素，最终这个小顶堆就是 TopK 数据了。（此法甚好）

• 堆是一个完全二叉树

• 每个节点的值都必须大于等于（或小于等于）其左右孩子节点的值

如果每个节点的值都大于等于左右孩子节点的值，这样的堆叫大顶堆；如果每个节点的值都小于等于左右孩子节点的值，这样的堆叫小顶堆。

上图中，左侧的堆是大顶堆，右侧的堆是小顶堆，我们还可以得出这个结论：对应大顶堆，堆顶一定是最大值；对于小顶堆，堆顶一定是最小值。

如何构建堆

我们在介绍二叉树的定义和存储的时候说到，由于完全二叉树的特殊性，可以通过数组来存储，堆也是完全二叉树，所以我们完全可以通过数组来存储。在使用数组存储堆的时候，把第一个索引位置留空，从第二个索引位置开始存储堆元素，这样，对于索引值为 i 的元素而言，其子节点索引分别为 2i 和 2i+1。
下面我们就来看如何在堆中插入新节点，以大顶堆为例，从叶子结点插入，如果比父级元素大，则与父级元素交换位置，依次类推，直到到达根节点（小顶堆恰好相反）：

注：构建堆的过程叫堆化。

堆排序

堆排序的过程其实就是不断删除堆顶元素的过程。如果构建的是大顶堆，逐一删除后堆顶元素构成的序列是从大到小排序；如果构建的是小顶堆，逐一删除堆顶元素后构成的序列是从小到大排序。而这其中的原理，就是我们在上一篇提到的：对于大顶堆，堆顶一定是最大值；对于小顶堆，堆顶一定是最小值。
但是这里有一个问题，每次从堆顶删除元素后，需要从子节点中取值补齐堆顶，依次类推，直到叶子节点，就会致使存储堆的数组出现「空洞」：

解决办法是将数组中的最后一个元素（最右边的叶子节点）移到堆顶，再重新对其进行堆化：

这样，就完美解决了「数组空洞」的问题。

复杂度分析

我们先看时间复杂度，对堆排序而言，分为两个阶段，一个是堆的构建，一个是堆顶元素的删除。对于 n 个节点的堆化而言，通过数组存储，对应的时间复杂度是 O(n)，对于堆顶元素的删除而言，需要遍历 n 个节点，并且，每次删除后需要重新堆化，对应的平均时间复杂度是 O(nlogn)。所以综合下来，堆排序的时间复杂度和快速排序、归并排序一样，是 O(nlogn)。

<?php
class Heap
{
    private $a = [];
    private $n;
    private $count;
      //初始化数组容量，元素个数
    public function __construct($capacity = 10)
    {
        $this->n = $capacity;
        $this->count = 0;
    }
    //构建大顶堆
    public function insert($data)
    {     //元素个数大于容量返回
        if ($this->count >= $this->n) {
            return false;
        }
        $this->count++;      //从下标一开始
        $this->a[$this->count] = $data; //赋值
        $i = $this->count;
        //调整元素的位置，如果插入的值大于它的根节点，交换
        while (floor($i / 2) > 0 && $this->a[floor($i / 2)] < $this->a[$i]) {
            $temp = $this->a[$i];
            $this->a[$i] = $this->a[floor($i / 2)];
            $this->a[floor($i / 2)] = $temp;
            $i = $i / 2;
        }
        return true;
    }
     //从堆顶移除元素，非原地对排序
    public function remove()
    {   //如果小于零则返回
        if ($this->count == 0)
            return false;
        $removeData = $this->a[1]; //堆顶元素赋值给额外数组
        $this->a[1] = $this->a[$this->count]; // 把最后值提到堆头
        $this->count--;
        $i = 1;  // 堆顶元素
        while (true) {
            $maxPos = $i;
            //判断当前根元素是否小于左孩子
            if ($i * 2 <= $this->count && $this->a[$i * 2] > $this->a[$i]) {
                $maxPos = 2 * $i;
            }
            //判断右孩子是否大于左孩子
            if ($i * 2 + 1 <= $this->count && $this->a[$i * 2 + 1] > $this->a[$maxPos]) {
                $maxPos = 2 * $i + 1;
            }
            //已经比孩子大，退出
            if ($maxPos == $i) {
                break;
            }
             //孩子元素跟父节点交换值
            $temp = $this->a[$i];
            $this->a[$i] = $this->a[$maxPos];
            $this->a[$maxPos] = $temp;
            $i = $maxPos;
        }
        //返回堆顶元素
        return $removeData;
    }
    public function __toString()
    {
        return json_encode(array_values($this->a));
    }
}
$heap = new Heap();
$data = range(1, 10);
shuffle($data);
foreach ($data as $num) {
    if (!$heap->insert($num)) {
        break;
    }
}
print_r($heap);
$sortedData = [];
while ($removedData = $heap->remove()) {
    $sortedData[] = $removedData;
}
print_r($sortedData);

赫夫曼树(二叉树典型应用）

理解定义：带权重的最优二叉树叫做”赫夫曼树”。带权路径长度（权重x路径求和）最小的树叫做赫夫曼树
典型应用：我们日常使用压缩和解压软件的频率可谓是非常高，而最基本的压缩算法 —— 赫夫曼编码，其中使用的二叉树就是赫夫曼树

我们通过一个例子来引入什么是赫夫曼树。
我们在中小学每年期末考试结束后都会领到成绩单，成绩单上列出我们考试分数的等级，比如优秀（>=90）、良好(>=80)、合格(>=60)、不合格(<60)，以某个班为例，总人数是100人，不同成绩区间的比例如下：

不考虑效率因素的话，我们可以这么实现成绩等级判定：

这种情况下，比例占80%以上的分数都需要经历三次以上的判断才能得到结果，显然不合理，对此，我们可以对判断逻辑进行改进：

大部分同学的成绩都在 80 分左右，因此我们判断的逻辑改成了先通过 80 分对成绩进行划分，看起来效率是提升了，这其中的原理是每个分数都要循环调用此逻辑，将 80 分放到入口判断，总体判断次数更少，效率更高。
这就是赫夫曼树的雏形。显然，上述流程图可以抽象为一棵二叉树，每个等级的人数看作路径权重，我们把带权路径长度（权重x路径求和）最小的树叫做赫夫曼树，把上面两个流程图抽象为带路径权重的二叉树如下：

二叉树 a 的带权路径长度是 15+215+340+430+410 = 315，二叉树 b 的带权路径长度是 240+35+153+230+102 = 220，这意味着，对于人数 100 的班级，通过第一种方式要做 315 次比较，对于第二种方式，只需要 220 次比较，显然二叉树 b 比二叉树 a 更优。

赫夫曼树的构建

当然，上述二叉树 b 还不是赫夫曼树，因为它不是最优的，赫夫曼树的构造方式如下：

1. 把有权值的节点按照从小到大顺序进行排序：A5、E10、B15、D30、C40；
2. 取最小的两个节点作为某个新节点 N1 的子节点，较小的作为左子结点；
3. 然后将 N1 替代 A5 和 E10，插入上述有序序列，保持从小到大排序：N115、B15、D30、C40；
4. 重复步骤2，将 N1 和 B 作为一个新节点 N2 的左右节点，依次类推，直到把所有节点纳入树中。

最终形成的二叉树如下所示：

对应的带权路径长度是 140+230+315+45+4*10 = 205，对于 100 个学生而言，需要进行 205 次判断。比前面的二叉树 b 更优，同时也是最优的二叉树，所以是赫夫曼树。

赫夫曼编码及其应用

们介绍了赫夫曼树的定义和构建，当然，赫夫曼不会闲到为了转化下成绩等级专门实现赫夫曼树，当年，他研究赫夫曼树是为了解决远距离通信（主要是电报）数据传输的最优问题。
比如，我们需要在网络上传输 BADCADEEFD 字符串序列给其他人，每个字符占一个字节，如果要压缩的话可以通过二进制编码的方式进行传输，这个字符串包含了 6 个字符：ABCDEF，我们可以用对应的二进制表示如下：

这样，真正传输的数字编码就是 001000011010000011100100101011，对方接收时按照 3 位一分来译码，如果文章很长，这个序列串也会非常长。
而事实上，不管是英文还是中文，不同字母或汉字的出现频率是不同的，我们能否参考上篇文章按照不同成绩区间分布概率不同构建赫夫曼树的方式将这里的字符编码进行优化呢？
答案是可以，这种通过赫夫曼树对字符数据进行编码的方式就叫做赫夫曼编码。
具体实现方式如下：
上述 BADCADEEFD 中不同字符的出现大致概率是这样的：

合起来是 100%，我们可以这样来构建赫夫曼树（按照上篇文章赫夫曼树构建规则构建）：

然后我们将权值左分支改为 0，右分支改为 1，对应的赫夫曼树如下：

我们按照这六个字母经过路径的权值对字母进行重新编码：

这样一来我们就得到了新的字符编码，这就是赫夫曼编码，我们通过赫夫曼编码对字符串 BADCADEEFD 进行重新编码：

• 原编码二进制串：001000011010000011100100101011（30个字符）
• 新编码二进制串：1001101101110100100100001（25个字符）

这样一来，我们的数据被压缩了，节省了约 17% 的传输成本，随着字符串长度增加，重复字符增多，效果更明显，并且重复字符越多，压缩效果越好。
最后，在接收方如何解码呢？赫夫曼编码的结果是不同字符编码长短不一，很容易混淆，这就要求发送方和接收方约定好同样的编码规则，就好比二战时期，我们情报人员都要保有同样的密码本一样。

图

图是最复杂的一个数据结构，掌握了图也就掌握了数据结构的精髓。
图（Graph）由顶点（Vertex）和边（Edge）组成。图中的元素叫顶点，图不能为空，在线性表中，相邻元素有前后关系，在树中，相邻元素有层次关系，在图中，任意两个元素之间都可能有关系，顶点之间的关系通过边来表示。图可以表示为 G(V,E)，其中 G 表示图，V 表示顶点的集合，E 表示边的集合。
下面就是一个典型的图：

其中字母标识的节点就是图的顶点，节点之间的连线就是图的边。

无向图与有向图

没有方向的边叫无向边，任意两个顶点之间都是无向边的图叫无向图，比如上面那个示例图就是无向图。在无向图中，任意两个顶点之间都有边的图叫无向完全图。
与之相对的，有方向的边叫有向边（也叫弧），任意两个顶点之间都是有向边的图叫有向图，例如下面这个图就是有向图：

在有向图中，任意两个顶点之间都有方向相反的两条有向边的图叫有向完全图。
按照边的数目，我们将边数很少的图叫稀疏图，边数很多的图叫稠密图。
有些图的边还拥有与其相关的数字，我们把这个数字叫做权，这种带权的图通常称作网。

顶点与边的关系

顶点的度指的是与顶点相连接的边数，整个图的度数是所有顶点度数之和。
在无向图中，边不分方向，边数是图的度数/2。
在有向图中，边有方向，按照方向将有向图顶点的度分为出度和入度，出度表示有多少条边是以这个顶点为起点指向其他顶点；入度表示有多少条边指向这个顶点。
在树中，顶点到任意节点的路径是唯一的，而在图中，顶点到任意顶点的路径却不是唯一的。比如上述示例有向图中，从 B 到 A 就有 B->A、B->C->A 两条路径，示例无向图中还有 B->C->D->A 这条路径。

连通图

在无向图 G 中，如果顶点 v 到顶点 v’ 有路径，则称 v 和 v’ 是连通的，如果任意两个顶点都是连通的，则称 G 是连通图。比如上述示例无向图就是连通图。
在有向图 G 中，对于每一对顶点，如果相互之间都存在路径，则 G 是强连通图。上述示例有向图不是强连通图，因为 A 到 D 存在路径，而 D 到 A 不存在。

图的典型应用

图的应用场景很多，比如社交网络中用户之间的关系，网络设备之间的拓扑结构，以及显示生活中形形色色的网：公路网、铁路网、地铁网等等，都可以通过图来表示。

图的存储：邻接矩阵和邻接表

由于图这种数据结构比较复杂，单纯的数组和链表已经无法表示了，需要通过更复杂的结构来存储。
今天，学院君简单为大家介绍两种存储图的方式，一种是基于数组，一种是基于链表，但是不是简单的数组和链表，下面我们就一起来看看到底是如何存储图的。

邻接矩阵

显然，通过一维数组是无法存储图的，因为图包含顶点和边，而且每个顶点都可能与其他顶点有关联，所以我们通过两个数组来存储图：一个一维数组用于存储所有顶点，一个二维数组来存储连接顶点的边/弧，边或弧连接的是两个顶点，所以需要二维数组来存储。我们把这种存储图的方式叫做邻接矩阵。

说概念很抽象，下面我们通过实例来演示，对于无向图而言，由于边没有方向，所以存储无向图边的二维数组是一个对称矩阵（矩阵是一个数学概念，一个 m x n 的矩阵是一个由 m 行 n 列元素排列成的矩形阵列）：

对于有向图而言，由于边是有方向的，我们将二维数组中指向某个顶点的元素值设置为 1，否则设置为 0，比如下面 v1v0 为 1，而 v0v1 为 0（注意存储顺序，先横后纵，横向表示某个顶点的出度，纵向表示某个顶点的入度）：

对于带权的有向图，要更复杂一些，在存储弧的二维数组中，相邻的顶点对应元素值等于权重（入度），自己指向自己的对应元素值为 0，否则等于无穷大（∞）：

对于邻接矩阵而言，初始化的时间复杂度等于边数组构建的复杂度，对于有 n 个顶点的图而言，时间复杂度是 O(n^2)，空间复杂度也是如此，而且如果图比较稀疏的话（稀疏图），边数组会存在巨大的空间浪费。但是优点是实现起来非常简单，对于稠密图或者非常简单的图来说，用邻接矩阵是比较方便的。

邻接表

既然稀疏图用邻接矩阵存储不合适，那要怎么存储呢？有了前面的数据结构基础，我们很容易会联想到基于链表替代边数组来存储边，这样就可以避免对空间的浪费了。这种存储方式还是通过一个一维数组来存储顶点，只是将边/弧通过链表来表示，我们把这种存储方式叫做邻接表。
对于无向图来说，通过邻接表来存储，可以这么实现：

我们在每个顶点上通过 data 保存数据，通过 firstedge 指向第一个邻接顶点，指向节点上 adjvex 存储的是对应顶点的数组下标，如果该顶点有多个邻接顶点，可以通过 next 指向下一个邻接顶点，如果没有的话，则将对应指针设置为空。
对于有向图来说，原理也是类似，只不过有向图的边有方向而已，链表指针指向基于出度，所以很容易计算出某个顶点的出度：

显然，邻接表的构建时间复杂度要比邻接矩阵好，对于一个有 n 个顶点和 e 条边的图而言，时间复杂度是 O(n+e)，而且不存在任何空间的浪费，比较高效，可用于存储任何图。
但邻接表也不是十全十美，对于有向图来说，如果要计算某个顶点的入度，需要遍历整个图才能实现，要解决这个问题，我们可以通过逆邻接表来实现。所谓逆邻接表，就是和邻接表相反，指针指向基于入度，比如上面这个有向图，我们可以这样通过逆邻接表来构建：

对于有权重的有向图（网图），还要通过一个额外的 weight 域来存储权重：

图的遍历

图的遍历主要有两种方式，一种是深度优先搜索，一种是广度优先搜索。

深度优先搜索

深度优先搜索定义

深度优先搜索（Depth First Search），简称 DFS，这种算法有点像走迷宫，沿着一条路径一直走，如果某个路径不通，则回到前驱节点，以此为出发点继续尝试下一条路径，以此类推，直到访遍所有顶点。
深度优先搜索也是这样，它从图的某个顶点出发，访问此顶点，然后从该顶点未被访问的邻接顶点出发，深度遍历图，在未遇到已访问过的重复顶点前，我们约定右手优先原则，一直往前走，遇到已经访问过的顶点，则回溯到前驱顶点，访问与其相邻路径对应的邻接顶点，继续做上述判断，依次类推，直到图中所有与该顶点路径想通的顶点都被访问到，如下图所示：

如果还有顶点未被访问，则将其作为起点，重复上述过程，直到图中所有顶点都被访问到。
下面我们用代码来实现这个过程。

通过邻接表实现图的存储

在实现深度优先搜索之前，我们先定义一个数据结构来存储图，这里我们采用邻接表的方式。
为此要创建链表类 LinkedList 及对应的节点类 Node：

/**
 * Class Node
 * 链表节点类
 */
class Node
{
    public $data;
    /**
     * @var Node
     */
    public $next;
    public function __construct($data = null)
    {
        $this->data = $data;
    }
}
/**
 * Class LinkedList
 * 链表类
 */
class LinkedList
{
    private $head = null;
    private $count = 0;
    public function __construct()
    {
        $emptyNode = new Node();
        $this->head = $emptyNode;
    }
    public function insert($data)
    {
        if ($this->head == null) {
            return;
        }
        $newNode = new Node($data);
        $newNode->next = $this->head->next;
        $this->head->next = $newNode;
        $this->count++;
    }
    public function remove(Node $node)
    {
        if ($node == null) {
            return false;
        }
        $preNode = $this->pre($node);
        $preNode->next = $node->next;
        $this->count--;
    }
    public function get($index)
    {
        if ($index >= $this->count) {
            return false;
        }
        $node = $this->head->next;
        $i = 0;
        while ($node) {
            if ($i == $index) {
                return $node;
            } else {
                $node = $node->next;
                $i++;
            }
        }
        return false;
    }
    public function pre(Node $node)
    {
        if ($node == null) {
            return false;
        }
        $preNode = $this->head;
        $curNode = $this->head->next;
        while ($curNode) {
            if ($curNode === $node) {
                return $preNode;
            } else {
                $preNode = $curNode;
                $curNode = $preNode->next;
            }
        }
        return false;
    }
    public function getSize()
    {
        return $this->count;
    }
    public function __toString()
    {
        $node = $this->head->next;
        $arr = [];
        $i = 0;
        while ($node) {
            $arr[] = 'Node[' . $i . ']:data=>' . $node->data . ',next=>' . json_encode($node->next);
            $i++;
            $node = $node->next;
        }
        return implode("\n", $arr);
    }
}

然后我们来定义一个 Graph 类通过邻接表来存储图：

/**
 * Class Graph
 * 通过邻接表存储图
 */
class Graph
{
    private $v;  # 顶点个数
    /**
     * @var LinkedList[]
     */
    private $adj = [];  # 邻接表
    private $found = false;
    public function __construct(int $v)
    {
        $this->v = $v;
        for ($i = 0; $i < $v; $i++) {
            $this->adj[$i] = new LinkedList();
        }
    }
    // 无向图同一条边要存两次
    public function addEdge($s, $t)
    {
        $this->adj[$s] = $t;
        $this->adj[$t] = $s;
    }
}

我们首先将所有顶点的邻接顶点设置为空链表，然后我们可以通过 addEdge 方法为图添加边（$s 和 $t 分别代表边的两个顶点），从而完成图的构建。
有了完整的图之后，就可以编写深度优先搜索方法对其进行遍历了。

通过代码实现深度优先搜索

我们在 Graph 类中定义深度优先搜索方法 dfs 如下：

public function dfs($s, $t)
{
    $this->found = false;
    for ($i = 0; $i <= $this->v; $i++) {
        $visited[$i] = 0;
    }
    for ($i = 0; $i <= $this->v; $i++) {
        $prev[$i] = -1;
    }
    $this->recurDfs($s, $t, $visited, $prev);
    $this->printPath($prev, $s, $t);
}
public function recurDfs($w, $t, $visited, $prev)
{
    if ($this->found == true) {
        return;
    }
    $visited[$w] = 1;
    if ($w == $t) {
        $this->found = true;
        return true;
    }
    for ($i = 0; $i < $this->adj[$w]->getSize(); $i++) {
        $q = $this->adj[$w]->get($i)->data;
        if (!$visited[$q]) {
            $prev[$q] = $w;
            $this->recurDfs($q, $t, $visited, $prev);
        }
    }
}
public function printPath($prev, $s, $t)
{
    if ($prev[$t] != -1 && $t != $s) {
        $this->printPath($prev, $s, $prev[$t]);
    }
    print $t;
}

我们先将每个顶点是否已经访问设置为 0，将每个顶点的前驱节点设置为 -1，然后通过一个递归方法 recurDfs 实现深度优先搜索算法，如果最终起点与终点重合则表示两个顶点之间的所有顶点已经遍历完毕，立即返回，否则继续搜索。
搜索完毕后，将路径信息通过 printPath 打印出来。这个测试任务交给你们自己去完成。
深度优先搜索的时间复杂度很显然是 O(v+e)，其中 v 表示顶点数，e 表示边数，需要额外的数组存储已访问顶点和前驱顶点，对应的空间复杂度是 O(v)。

广度优先搜索

广度优先搜索（Breadth First Search），简称 BFS，我们以在家里房间里找钥匙为例来对比说明深度优先搜索和广度优先搜索，深度优先搜索好比我们从某个房间（顶点）开始，先把一个房间的所有角落找遍，再从下一个相邻房间开始继续找，依次类推，但这有时候并不是最佳方案，我们可以换一种思路，先大致扫一下每个房间的常见位置，如果都没有的话才继续更深入的寻找，这种遍历方式就是广度优先搜索。
还可以通过树的遍历来类比图的遍历，前序遍历类似深度优先搜索，层序遍历类似广度优先搜索，下面我们以一个图为例来说明，这样更加形象：

左图是我们要遍历的图，右图是以广度优先搜索对图进行遍历，我们把 A 作为第一层，B、F 作为第二层，C、I、G、E 看作第三层，D、H 看作第四层，每次遍历一层。
这与我们上一篇讲述的深度优先搜索显然不同，深度优先搜索会把某个顶点的所有相邻顶点访问完才继续下一个顶点的访问，广度优先搜索则不然，它是按照「层级」遍历图的节点，最终也能够遍历完所有节点。

广度优先搜索算法实现(遇到了再理解)

广度优先搜索的时间复杂度和深度优先搜索一样，也是 O(v+e)，其中 v 表示顶点数，e 表示边数，需要额外的数组存储已访问顶点和前驱顶点，对应的空间复杂度是 O(v)。
广度优先搜索和深度优先搜索的复杂度完全一样，没有优劣之分，具体使用哪种搜索方式，以实际情况为准。

最小生成树的定义和应用场景

带权的图叫做网，我们把构造连通网（带权连通图）的最小代价生成树叫做最小生成树。这个最小代价指的是通过 n-1 条边具有把 n 个顶点的连通图连接起来，并且使所有边的权值和最小。如下图所示，实线部分就是最小生成树：

最小生成树的应用场景很多，小到我们要来个欧洲十国游，怎么规划路径让交通费用最低，大到国家的电力网、公路网、通信网，怎么规划路径可以让建设成本最低，学习了最小生成树后，你就可以通过算法来计算出最佳路径了，不仅如此，所有涉及连接网络中所有节点的最优路径问题，都可以通过最小生成树来处理。
最小生成树有多种实现算法，我们这里介绍两种比较常见的：普里姆算法（Prim）和克鲁斯卡尔算法（Kruskal）。

最短路径及实现算法

在日常生活中，我们经常面临路径选择的问题，比如从杭州到北京，可以选择汽车、火车、飞机，甚至还可以坐公交车（这不是笑话，最近网上就流传一个从杭州回临沂，转了 35 班公交车，行程 660 多公里，历时 7 天的神奇春运回家路），对于不同的选择，意味着不同的路径，不同的路径意味着不同的成本，这个成本有时间成本，也有经济成本，不差钱的可以选择时间成本低的，比如坐飞机，经济不那么宽裕却有时间的，可以做公交车，我们把杭州和北京看作图上的两个顶点（中间可能会经过其它城市，即多个顶点），把时间成本或者经济成本看作权重，那么从杭州到北京的路径规划就可以抽象为今天我们要分享的话题 —— 图的最短路径问题。

最短路径的实现也有多种算法，和最小生成树一样，两种最常见的实现算法：迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。

拓扑排序的定义及其应用场景（AOV网）

前面介绍的最小生成树和最短路径都是有环图的应用，接下来我们来介绍无环图的应用，所谓无环图，就是图中没有回路。无环图两个常见的应用就是拓扑排序和关键路径。
我们先来看看拓扑排序。
在日常生活中，我们通常会把软件开发、生产流程、网络设备互联都当成一个项目工程来对待，所有工程都可以分为若干个子工程（或者称之为「活动」），这些子工程之间往往会有一些条件约束，比如其中某些活动必须在另一些活动完成之后才能进行。下面是一个简单的软件开发流程图：

我们将整个流程抽象为图这种数据结构，则每个子工程节点就是图的顶点，连接子工程的前后约束就是图的边（并且是有方向的边），并且工程有起始节点，也有结束节点，并且，首尾不会相连，所以综合来看，这样的工程图，一定是无环的有向图。
在一个表示工程的有向图中，用顶点表示活动，用弧（有方向的边）表示活动之间的优先关系，这样的以顶点表示活动的有向图，我们称之为 AOV 网（Activity On Vertex Network）。
有了以上的准备工作，下面我们正式介绍拓扑排序的概念。
设 G=(V,E)（其中 V 表示顶点集合，E 表示弧集合）是一个具有 n 个顶点的有向图，V 集合中的顶点满足从顶点 i 到顶点 j 之间有一条路径，并且在顶点序列中 i 一定在 j 之前，则我们称这样的序列为一个拓扑序列。
而所谓的拓扑排序，就是对有向图构造拓扑序列的过程。
构造结果中如果全部顶点都被输出，则说明它是不存在回路的 AOV 网；否则说明存在回路，不是 AOV 网。
对于不存在回路的 AOV 网，可以应用在各种不同的工程或项目流程图中，满足各种场景的需要，所以拓扑排序在工程中非常有实用价值。

关键路径的定义及其应用场景（AOE网）

前面介绍的拓扑排序主要是为了解决一个工程是否可以顺利进行的问题，但有时候我们还要解决工程完成需要的最短时间问题。
我们要对一个流程图计算最短时间，就要分析流程之间的拓扑关系，并且找到当中最关键的流程，这个流程的时间就是最短时间。
尽管 AOE 网和 AOV 网都是针对工程进行建模的，但是两者有明显的不同，主要体现在 AOV 网是顶点表示活动的网，它只描述活动之间的制约关系；而 AOE 网是边表示活动的网，边上的权值表示活动持续的时间，因此 AOE 网建立在活动之间制约关系没有矛盾的基础之上，再来分析整个工程至少需要多少时间，或者为了缩短完成整个工程所需时间，应当加快哪些活动。这也是 AOE 网的主要应用场景。

学习总结和感受

从简单的数组到复杂的图结构。可以感受到数据结构的实际生产中是多么的重要，也就是掌握了数据结构和算法的程序员具备”造轮子”的生产能力。 进而在不断优化数据结构的同时，衍生出很多新技术。所以要想有所作为必须掌握这些数据结构实现的算法以及原理。不然只能使用别人的轮子！
一等程序员造轮子
二等程序员改造轮子
三等程序员日复一日使用轮子