优先队列（Priority Queue）
特点
能保证每次取出的元素都是队列中优先级别最高的。优先级别可以是自定义的，例如，数据的数值越大，优先级越高；或者数据的数值越小，优先级越高。优先级别甚至可以通过各种复杂的计算得到。
应用场景
从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分乃至全部的数据。
举例：任意一个数组，找出前 k 大的数。
解法 1：先对这个数组进行排序，然后依次输出前 k 大的数，复杂度将会是 O(nlogn)，其中，n 是数组的元素个数。这是一种直接的办法。
解法2：使用优先队列，复杂度优化成O(k+nlogk)。当数据量很大（即n很大），而k相对较小的时候，显然，利用优先队列能有效地降低算法复杂度。因为要找出前k大的数，并不需要对...
实现
优先队列的本质是一个二叉堆结构。堆在英文里叫BinaryHeap，它是利用一个数组结构来实现的完全二叉树。换句话说，优先队列的本质是一个数组，数组里的每个元素既有可能是其他元素的父节点，也有可能是...
牢记下面优先队列有三个重要的性质：
-
数组里的第一个元素 array[0] 拥有最高的优先级别。
-
给定一个下标 i，那么对于元素 array[i] 而言：
-
它的父节点所对应的元素下标是 (i-1)/2
-
它的左孩子所对应的元素下标是 2×i + 1
-
它的右孩子所对应的元素下标是 2×i + 2
- 数组里每个元素的优先级别都要高于它两个孩子的优先级别。
优先队列最基本的操作有两个。
- 向上筛选（sift up / bubble up）
- 当有新的数据加入到优先队列中，新的数据首先被放置在二叉堆的底部。
- 不断进行向上筛选的操作，即如果发现该数据的优先级别比父节点的优先级别还要高，那么就和父节点的元素相互交换，再接着往上进行比较，直到无法再继续交换为止。
时间复杂度：由于二叉堆是一棵完全二叉树，并假设堆的大小为 k，因此整个过程其实就是沿着树的高度往上爬，所以只需要 O(logk) 的时间。
- 向下筛选（sift down / bubble down）
- 当堆顶的元素被取出时，要更新堆顶的元素来作为下一次按照优先级顺序被取出的对象，需要将堆底部的元素放置到堆顶，然后不断地对它执行向下筛选的操作。
- 将该元素和它的两个孩子节点对比优先级，如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换，然后反复进行下去，直到无法继续交换为止。
时间复杂度：整个过程就是沿着树的高度往下爬，所以时间复杂度也是 O(logk)。
因此，无论是添加新的数据还是取出堆顶的元素，都需要 O(logk) 的时间。
初始化
优先队列的初始化是一个最重要的时间复杂度，是分析运用优先队列性能时必不可少的，也是经常容易弄错的地方。
举例：有 n 个数据，需要创建一个大小为 n 的堆。
误区：每当把一个数据加入到堆里，都要对其执行向上筛选的操作，这样一来就是 O(nlogn)。
解法：在创建这个堆的过程中，二叉树的大小是从 1 逐渐增长到 n 的，所以整个算法的复杂度经过推导，最终的结果是 O(n)。
image.png
注意：算法面试中是不要求推导的，你只需要记住，初始化一个大小为 n 的堆，所需要的时间是 O(n) 即可。
图（Graph）
基本知识点
图可以说是所有数据结构里面知识点最丰富的一个，最基本的知识点如下。
- 阶（Order）、度：出度（Out-Degree）、入度（In-Degree）
- 树（Tree）、森林（Forest）、环（Loop）
- 有向图（DirectedGraph）、无向图（UndirectedGraph）、完全有向图、完全无向图
- 连通图（ConnectedGraph）、连通分量（Connected Component）
- 存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）
围绕图的算法也是五花八门。
- 图的遍历：深度优先、广度优先
- 环的检测：有向图、无向图
- 拓扑排序
- 最短路径算法：Dijkstra、Bellman-Ford、FloydWarshall
- 连通性相关算法：Kosaraju、Tarjan、求解孤岛的数量、判断是否为树
- 图的着色、旅行商问题等
以上的知识点只是图论里的冰山一角，对于算法面试而言，完全不需要对每个知识点都一一掌握，而应该有的放矢地进行准备。
必会知识点
根据长期的经验总结，以下的知识点是必须充分掌握并反复练习的。
- 图的存储和表达方式：邻接矩阵（AdjacencyMatrix）、邻接链表（AdjacencyList）
- 图的遍历：深度优先、广度优先
- 二部图的检测（Bipartite）、树的检测、环的检测：有向图、无向图
- 拓扑排序
- 联合-查找算法（Union-Find）
- 最短路径：Dijkstra、Bellman-Ford
其中，环的检测、二部图的检测、树的检测以及拓扑排序都是基于图的遍历，尤其是深度优先方式的遍历。而遍历可以在邻接矩阵或者邻接链表上进行，所以掌握好图的遍历是重中之重！因为它是所有其他图论算法的基础。
至于最短路径算法，能区分它们的不同特点，知道在什么情况下用哪种算法就很好了。对于有充足时间准备的面试者，能熟练掌握它们的写法当然是最好的。
前缀树（Trie）
应用场景
前缀树被广泛地运用在字典查找当中，也被称为字典树。
举例：给定一系列字符串，这些字符串构成了一种字典，要求你在这个字典当中找出所有以“ABC”开头的字符串。
解法1：暴力搜索
直接遍历一遍字典，然后逐个判断每个字符串是否由“ABC”开头。假设字典很大，有 N 个单词，要对比的不是“ABC”，而是任意的，那不妨假设所要对比的开头平均长度为 M，那么时间复杂度是 O(M×N)。
解法2：前缀树
如果用前缀树头帮助对字典的存储进行优化，那么可以把搜索的时间复杂度下降为O(M)，其中M表示字典里最长的那个单词的字符个数，在很多情况下，字典里的单词个数N是远远大于M 的。因此，前缀树在这种场合中是非常高效的。
经典应用
-
网站上的搜索框会罗列出以搜索文字作为开头的相关搜索信息，这里运用了前缀树进行后端的快速检索。
-
汉字拼音输入法的联想输出功能也运用了前缀树。
举例：假如有一个字典，字典里面有如下词："A"，"to"，"tea"，"ted"，"ten"，"i"，"in"，"inn"，每个单词还能有自己的一些权重值，那么用前缀树来构建这个字典将会是如下的样子：
性质
- 每个节点至少包含两个基本属性。
-
children：数组或者集合，罗列出每个分支当中包含的所有字符
-
isEnd：布尔值，表示该节点是否为某字符串的结尾
2.前缀树的根节点是空的所谓空，即只利用到这个节点的children属性，即只关心在这个字典里，有哪些打头的字符。
3.除了根节点，其他所有节点都有可能是单词的结尾，叶子节点一定都是单词的结尾。
实现
前缀树最基本的操作就是两个：创建和搜索。
- 创建
- 遍历一遍输入的字符串，对每个字符串的字符进行遍历- - 从前缀树的根节点开始，将每个字符加入到节点的children字符集当中。
- 如果字符集已经包含了这个字符，则跳过。
- 如果当前字符是字符串的最后一个，则把当前节点的 isEnd 标记为真。
由上，创建的方法很直观。
前缀树真正强大的地方在于，每个节点还能用来保存额外的信息，比如可以用来记录拥有相同前缀的所有字符串。因此，当用户输入某个前缀时，就能在 O(1) 的时间内给出对应的推荐字符串。
- 搜索
与创建方法类似，从前缀树的根节点出发，逐个匹配输入的前缀字符，如果遇到了就继续往下一层搜索，如果没遇到，就立即返回。
线段树（Segment Tree）
举例：假设有一个数组array[0…n-1]，里面有n个元素，现在要经常对这个数组做两件事。
- 更新数组元素的数值
- 求数组任意一段区间里元素的总和（或者平均值）
解法 1：遍历一遍数组。
- 时间复杂度 O(n)。
解法 2：线段树。
-
线段树，就是一种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和。
-
适用于数据很多，而且需要频繁更新并求和的操作。
-
时间复杂度 O(logn)。
实现
举例：数组是 [1, 3, 5, 7, 9, 11]，那么它的线段树如下。
根节点保存的是从下标 0 到下标 5 的所有元素的总和，即 36。左右两个子节点分别保存左右两半元素的总和。按照这样的逻辑不断地切分下去，最终的叶子节点保存的就是每个元素的数值。
解法：
1.更新数组里某个元素的数值
从线段树的根节点出发，更新节点的数值，它保存的是数组元素的总和。修改的元素有可能会落在线段树里一些区间里，至少叶子节点是肯定需要更新的，所以，要做的是从根节点往下，判断元素的下标是否在左边还是右边，然后更新分支里的节点大小。因此，复杂度就是遍历树的高度，即 O(logn)。
2.对数组某个区间段里的元素进行求和
方法和更新操作类似，首先从根节点出发，判断所求的区间是否落在节点所代表的区间中。如果所要求的区间完全包含了节点所代表的区间，那么就得加上该节点的数值，意味着该节点所记录的区间总和只是所要求解总和的一部分。接下来，不断地往下寻找其他的子区间，最终得出所要求的总和。
建议：线段树的实现书写起来有些繁琐，需要不断地练习。
树状数组（Fenwick Tree / Binary Indexed Tree）
实现
举例：假设有一个数组 array[0 … n-1]， 里面有 n 个元素，现在要经常对这个数组做两件事。
-
更新数组元素的数值
-
求数组前 k 个元素的总和（或者平均值）
解法1：线段树。
- 线段树能在O(logn)的时间里更新和求解前k个元素的总和。
解法2：树状数组。
- 该问题只要求求解前k个元素的总和，并不要求任意一个区间。
- 树状数组可以在 O(logn) 的时间里完成上述的操作。
- 相对于线段树的实现，树状数组显得更简单。
特点
树状数组的数据结构有以下几个重要的基本特征。
- 它是利用数组来表示多叉树的结构，在这一点上和优先队列有些类似，只不过，优先队列是用数组来表示完全二叉树，而树状数组是多叉树。
- 树状数组的第一个元素是空节点。
- 如果节点 tree[y] 是 tree[x] 的父节点，那么需要满足条件：y = x - (x & (-x))。
建议：由于树状数组所解决的问题跟线段树有些类似，所以不花篇幅进行问题的讨论。LeetCode上有很多经典的题目可以用树状数组来解决，比如LeetCode第308题，求一个动态变化的二维矩阵里，任意子矩阵里的数的总和。
总结
1.优先队列
经常出现在考题里的，它的实现过程比较繁琐，但是很多编程语言里都有它的实现，所以在解决面试中的问题时，实行“拿来主义”即可。鼓励你自己练习实现一个优先队列，在实现它的过程中更好地去了解它的结构和特点。
2.图
被广泛运用的数据结构，很多涉及大数据的问题都得运用到图论的知识。比如在社交网络里，每个人可以用图的顶点表示，人与人直接的关系可以用图的边表示；再比如，在地图上，要求解从起始点到目的地，如何行驶会更快捷，需要运用图论里的最短路径算法。
3.前缀树
出现在许多面试的难题当中。
因为很多时候你得自己实现一棵前缀树，所以你要能熟练地书写它的实现以及运用它。
4.线段树和树状数组
应用场合比较明确。
例如，问题变为在一幅图片当中修改像素的颜色，然后求解任意矩形区间的灰度平均值，那么可以考虑采用二维的线段树了。
网友评论