优秀的算法往往取决于你采用哪种数据结构，那么在这节课里，我们将重点介绍几种高级的数据结构，它们是：优先队列、图、前缀树、分段树以及树状数组。
之所以称它们为高级的数据结构，是因为它们的实现要比那些常用的数据结构要复杂得多，这些高级的数据结构能够让你在处理一些复杂问题的过程中多拥有一把利器。同时，掌握好它们的性质以及所适用的场合，在分析问题的时候回归本质，那么很多题目都能迎刃而解了。
下面我们就来一一介绍它们。
优先队列（Priority Queue）
图片: https://uploader.shimo.im/f/l…
首先我们来介绍一下优先队列。— 用图来说明
和普通队列不同的是，优先队列最大的作用是能保证每次取出的元素都是队列中优先级别最高的，这个优先级别可以是自定义的，例如，数据的数值越大，优先级越高，或者是数据的数值越小，优先级越高，优先级别甚至可以通过各种复杂的计算得到。
优先队列最常用的场景是从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分的乃至全部的数据。
例如，任意给定一个数组，要求找出前 k 大的数。试想一下，最直接的办法就是先对这个数组进行排序，然后依次输出前 k 大的数，这样的复杂度将会是 O(nlogn)，其中，n 是数组的元素个数。
有没有更好的办法呢？如果我们借用优先队列，就能将复杂度优化成 O(k + nlogk)，当数据量很大（即 n 很大），而 k 相对较小的时候，显然，利用优先队列能有效地降低算法复杂度，其本质就在于，要找出前 k 大的数，我们并不需要对所有的数进行排序。现在问题来了，这个复杂度是如何计算出来的呢？要理解它，我们先来看看优先队列的实现方法。
优先队列的本质是一个二叉堆结构，堆在英文里叫 Binary Heap，它是利用一个数组结构来实现的完全二叉树。换句话说，优先队列的本质是一个数组，数组里的每个元素既有可能是其他元素的父节点，也有可能是其他元素的子节点，而且，每个父节点只能有两个子节点，这就很像一棵二叉树的结构了。
这里有三个重要的性质需要牢记：
数组里的第一个元素 array[0]拥有最高的优先级别。
给定一个下标 i，那么对于元素 array[i] 而言:
它的父节点所对应的元素下标是 (i-1) / 2
它的左孩子所对应的元素下标是 2*i + 1
它的右孩子所对应的元素下标是 2*i + 2
数组里每个元素的优先级别都要高于它两个孩子的优先级别。
图片: https://uploader.shimo.im/f/7…
优先队列最基本的操作就是两个：
向上筛选（sift up / bubble up）
向下筛选（sift down / bubble down）
什么是向上筛选呢？当有新的数据加入到优先队列中，新的数据首先被放置在二叉堆的底部，然后不断地对它进行向上筛选的操作，即如果发现它的优先级别比父节点的优先级别还要高，那么就和父节点的元素相互交换，再接着网上进行比较，直到无法再继续交换为止。由于二叉堆是一棵完全二叉树，并假设堆的大小为 k，因此整个过程其实就是沿着树的高度网上爬，所以只需要 O(logk)的时间。
3
/ \
5 9 3, 5, 9
3
/ \
5 9 3,5,9,2
/
2
3
/ \
2 9 3,2,9,5
/
5
2
/ \
3 9 2,3,9,5
/
5
如何进行向下筛选呢？当堆顶的元素被取出时，我们要更新堆顶的元素来作为下一次按照优先级顺序被取出的对象，我们所需要的是将堆底部的元素放置到堆顶，然后不断地对它执行向下筛选的操作，在这个过程中，该元素和它的两个孩子节点对比，看看哪个优先级最高，如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换，然后反复进行下去，直到无法继续交换为止，整个过程就是沿着树的高度往下爬，所以时间复杂度也是 O(logk)。
2
/ \
3 9 2,3,9,5
/
5
5
/ \
3 9 5,3,9
3
/ \
5 9 3,5,9
因此，无论是添加新的数据还是取出堆顶的元素，都需要 O(logk)的时间。
另外一个最重要的时间复杂度是优先队列的初始化，这是分析运用优先队列性能时必不可少的，也是经常容易弄错的地方。
假设我们有 n 个数据，我们需要创建一个大小为 n 的堆，乍一看，每当把一个数据加入到堆里，我们都要对其执行向上筛选的操作，这样以来就是 O(nlogn)。但是，在创建这个堆的过程中，二叉树的大小是从 1 逐渐增长到 n 的，所以整个算法的复杂度是：
图片: https://uploader.shimo.im/f/q…
经过进一步的推导，最终的结果是 O(n)。算法面试中是不要求推导的，你只需要记住，初始化一个大小为 n 的堆，所需要的时间是 O(n)即可。
注：
向上筛选，用这个静态图
3
/ \
5 9
/
2
例题分析
LeetCode 第 347 题. Top K Frequent Words 从一系列单词中找出使用频率最高的前 K 个单词
这道题的输入是一个字符串数组，数组里的元素可能会重复一次甚至多次，要求按顺序输出前 K 个出现次数最多的字符串。
当我们拿到这个题目的时候，看到”前 K 个“这样的字眼就应该很自然地联想到运用优先队列。
那么优先级别怎么计算呢？让我们来分析一下，优先级别可以由字符串出现的次数来决定，出现的次数越多，优先级别越高，反之越低。
统计词频的最佳数据结构就是哈希表（Hash Map），利用一个哈希表，我们就能快速的知道每个单词出现的次数。
然后将单词和其出现的次数作为一个新的对象来构建一个优先队列，那么这个问题就很轻而易举地解决了。
可以看到，解这类求前 K 个的题目，关键是看如何定义优先级以及优先队列中元素的数据结构。这道题可以说是利用优先对列处理问题的典型，建议好好看看。
Desk (3)
/ \
car(2) book(1)
图（Graph）
图片: https://uploader.shimo.im/f/f…
接下来让我们看看如何准备图论的知识点。
图可以说是所有数据结构里面知识点最丰富的一个，最基本的知识点就有如下这些：
阶（Order）、度：出度（Out-Degree）、入度（In-Degree）
树（Tree）、森林（Forest）、环（Loop）
有向图（Directed Graph）、无向图（Undirected Graph）、完全有向图、完全无向图
连通图（Connected Graph）、连通分量（Connected Component）
存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）
围绕图的算法也是五花八门：
图的遍历：深度优先、广度优先
环的检测：有向图、无向图
拓扑排序
最短路径算法：Dijkstra、Bellman-Ford、Floyd Warshall
连通性相关算法：Kosaraju、Tarjan、求解孤岛的数量、判断是否为树
图的着色、旅行商问题等
以上的知识点只是图论里的冰山一角，对于算法面试而言，我们完全不需要对每个知识点都一一掌握，而应该有的放矢地进行准备。
力扣里边有许多关于图论的算法题，而且都是非常经典的题目，根据我的归纳和经验概括，以下的知识点是必须充分掌握并反复练习的：
图的存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）
图的遍历：深度优先、广度优先
二部图的检测（Bipartite）、树的检测、环的检测：有向图、无向图
拓扑排序
联合 - 查找算法（Union-Find）
最短路径：Dijkstra、Bellman-Ford
其中，环的检测、二部图的检测、树的检测以及拓扑排序都是基于图的遍历，尤其是深度优先方式的遍历。而遍历可以在邻接矩阵或者邻接链表上进行，所以掌握好图的遍历是重中之重！因为它是所有其他图论算法的基础。
至于最短路径算法，能区分它们的不同特点，知道在什么情况下用哪种算法就很好了。对于有充足时间准备的面试者，能熟练掌握它们的写法当然是最好的。
下面让我们通过一道例题来复习图论的知识。
例题分析
LeetCode 第 785 题. Is Graph Bipartite? 检测一个图是否为二部图
什么是二部图？
图片: https://uploader.shimo.im/f/s…
所谓二部图，就是在图里面，图的所有顶点可以分成两个子集 U 和 V，子集里的顶点互不直接相连，图里面所有的边，一头连着子集 U 里的顶点，一头连着子集 V 里的顶点。
现在，给定一个任意的图，如何判断它是否为二部图呢？很显然，我们必须要对这个图进行一次遍历。遍历的方法有深度优先以及广度优先。关于深度优先和广度优先算法，我们将在第 06 节课进行详细地讨论。
基本的思想是，我们来给图里的顶点涂上颜色，子集 U 里的顶点都涂上红色，子集 V 里的顶点都涂上蓝色。下面我们开始遍历这个图的所有顶点了，想象一下我们手里握有两种颜色（红色和蓝色）的画笔，每次我们交替地给遍历当中遇到的顶点涂上颜色，如果这个顶点还没有颜色，那我们就给它涂上颜色，然后换成另外一支画笔，遇到下一个顶点的时候，如果发现这个顶点已经涂上了颜色，而且颜色跟我手里画笔的颜色不同，那么表示这个顶点它既能在子集 U 里，也能在子集 V 里，所以，它不是一个二部图。
前缀树（Trie）
图片: https://uploader.shimo.im/f/N…
接下来我们来看看前缀树，它的英文念 Trie。
前缀树也被称为字典树，因为这种数据结构被广泛地运用在字典查找当中。什么是字典查找呢？举个例子，给定一系列字符串，这些字符串构成了一种字典，要求你在这个字典当中找出所有以“ABC”开头的字符串。
对于这样的问题，也许你会认为，那不是很简单嘛，直接遍历一遍字典，然后逐个判断每个字符串是否由“ABC”开头就好了。假设字典很大，有 N 个单词，我们要对比的不是“ABC”，而是任意的，那我们不妨假设所要对比的开头平均长度为 M，那么这种暴力的搜索算法，时间复杂度是 O(M*N)。
如果我们用前缀树头帮助我们对字典的存储进行优化，那么我们可以把搜索的时间复杂度下降为 O(M)，其中 M 表示字典里最长的那个单词的字符个数，在很多情况下，字典里的单词个数 N 是远远大于 M 的。因此，前缀树在这种场合中是非常高效的。
前缀树的经典应用有哪些呢？
我们在网站上的搜索框中输入要搜索的文字时，搜索框会罗列出以搜索文字作为开头的相关搜索信息，这里就运用到了前缀树，在后端进行快速地检索。
另外，我们经常会用到汉字拼音输入法，它的联想输出功能也运用到了前缀树。
好，既然前缀树如此强大，那就让我们来看看它的结构吧。让我们通过一个例子来深入理解它，假如我们有一个字典，字典里面有如下单词：”A”，”to”，”tea”，”ted”，”ten”，”i”，”in”，”inn”，每个单词还能有自己的一些权重值，那么用前缀树来构建这个字典将会是如下的样子：
图片: https://uploader.shimo.im/f/0…
前缀树有如下几个重要的性质：
每个节点至少包含两个基本属性：
children：数组或者集合，罗列出每个分支当中包含的所有字符
isEnd: 布尔值，表示该节点是否为某字符串的结尾
前缀树的根节点是空的，所谓空，也就是说我们只利用到了这个节点的 children 属性，即我们只关心在这个字典里，有哪些打头的字符。
除了根节点，其他所有节点都有可能是单词的结尾，叶子节点一定都是单词的结尾。
前缀树最基本的操作就是两个：创建和搜索，下面我们就分别来谈谈它们。
创建前缀树的方法其实很直观，遍历一遍输入的字符串，对每个字符串的字符进行遍历，在遍历的过程中，我们从前缀树的根节点开始，将每个字符加入到节点的 children 字符集当中，如果字符集已经包含了这个字符，就可以跳过，如果当前字符是字符串的最后一个，那么就把当前节点的 isEnd 标记为真。
前缀树真正强大的地方在于，每个节点还能用来保存额外的信息，比如可以用来记录拥有相同前缀的所有字符串。这样一来，当用户输入某个前缀时，我们就能在 O(1)的时间内给出对应的推荐字符串。
创建好前缀树之后，搜索就变得容易了，方法类似，我们从前缀树的根节点出发，逐个匹配输入的前缀字符，如果遇到了就继续往下一层搜索，如果没遇到，就立即返回。
例题分析
LeetCode 第 212 题：Word Search II 单词查找 II
这是一道出现较为频繁的难题，题目给出了一个二维的字符矩阵，然后还给出了一个字典，现在要求在这个字符矩阵中找到出现在字典里的单词。比如我们有如下的字符矩阵：
board = [
[‘o’, ‘a’, ‘a’, ‘n’],
[‘e’, ‘t’, ‘a’, ‘e’],
[‘i’, ‘h’, ‘k’, ‘r’],
[‘i’, ‘f’, ‘l’, ‘v’]
]
字典是 = [“oath”, “pea”, “eat”, “rain”]
要求输出: [“eat”,”oath”]
解这道题目的基本思想是，由于字符矩阵的每个点都能作为一个字符串的开头，所以我们必须得尝试从矩阵中的所有字符出发，上下左右一步步地走，然后去和字典进行匹配，如果发现那些经过的字符能组成字典里的单词，我们就把它记录下来。
那么，分别从矩阵的每个字符出发，上下左右一步步地走，我们可以借用深度优先的算法。关于深度优先算法，我们将在第 06 节课深入探讨，如果你对它不熟悉，可以把它想象成走迷宫。
好，基本的算法有了，那么还剩下一个问题，就是如何和字典匹配呢？直观的做法是每次都循环遍历字典，看看是否存在字典里面，如果我们把输入的字典变为哈希集合的话，似乎只需要 O(1)的时间就能完成匹配。
但是，这样的对比并不能进行前缀的对比，也就是说，我们必须每次都要进行一次全面的深度优先搜索，或者搜索的长度为字典里最长的字符串长度，这样还是不够高效。假如我们在矩阵里遇到了一个字符”V”，而我们的字典里根本就没有以“V”开头的字符串，那么我们根本就不需要将深度优先搜索进行下去，这样一来，可以帮助我们大大地提高搜索效率。
刚才我们提到了对比字符串的前缀，你应该能想到我们需要借助前缀树来帮我们重新构建字典了吧。构建好了前缀树之后，每次我们从矩阵里的某个字符出发进行搜索的时候，同步地对前缀树进行对比，如果发现字符一直能被找到，就继续进行下去，一步一步地匹配，直到在前缀树里发现一个完整的字符串，把它输出即可。
分段树（Segment Tree）
图片: https://uploader.shimo.im/f/3…
接下来我们来看看分段树。
要理解好什么是分段树以及为什么会有这样的数据结构，让我们从一个问题出发进行深入的探讨吧。
假设我们有一个数组 array[0 … n-1]，里面有 n 个元素，现在我们要经常对这个数组做两件事：
更新数组元素的数值
求数组任意一段区间里元素的总和（或者平均值）
我们知道，更新数组元素的数值总能在 O(1)的时间内完成，对于求数组元素的总和，直观上看必须遍历一遍数组，所以平均得用 O(n)的时间。那么对于数据很多，而且需要频繁地更新并求和的操作，有没有更好的办法呢？答案就是分段树。
分段树能让我们在 O(logn)的时间里更新元素的数值以及在 O(logn)的时间里完成对数组的求和。
所谓分段树，就是一种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和。例如，数组是[1, 3, 5, 7, 9, 11]，那么它的分段树就是：
图片: https://uploader.shimo.im/f/O…
可以看出，根节点保存的是从下标 0 到下标 5 的所有元素的总和，即 36，它的左右两个子节点分别保存左右两半元素的总和，按照这样的逻辑不断地切分下去，最终的叶子节点保存的就是每个元素的数值。
当我们更新数组里某个元素的数值时，我们得从分段树的根节点出发，更新节点的数值，因为它保存的是数组元素的总和。接下来，修改的元素有可能会落在分段树里一些区间里，至少叶子节点是肯定需要更新的，所以，我们要做的是从根节点往下，判断元素的下标是否在左边还是右边，然后更新分支里的节点大小。因此，复杂度就是遍历树的高度，即 O(logn)。
完成了元素数值的更新之后，我们要对数组某个区间段里的元素进行求和了。方法和更新操作类似，首先从跟节点出发，判断所求的区间是否落在节点所代表的区间中，如果所要求的区间完全包含了节点所代表的区间，那么就得加上该节点的数值，意味着该节点所记录的区间总和只是我们所要求解总和的一部分。接下来，不断地往下寻找其他的子区间，最终得出所要求的总和。
分段树的实现在书写起来有些繁琐，需要不断地练习才能加深印象。
例题分析
LeetCode 第 315 题：Count of Smaller Numbers After Self
题目看起来非常简单，给定一个数组 nums，里面都是一些整数，现在要求打印输出一个新的数组 counts，counts 数组的每个元素 counts[i]表示 nums 中第 i 个元素右边有多少个数小于 nums[i]。
例如：输入数组是[5, 2, 6, 1]，应该输出的结果是[2, 1, 1, 0]。什么意思呢？比如对于 5 来说，它的右边有两个数比它小，分别是 2 和 1，所以输出的结果中，第一个元素是 2，对于 2 来说，右边只有 1 比它小，所以第二个元素是 1，以此类推。
理解了问题之后，我们来看看如何借用分段树来帮助我们。
既然是分段树，我们就得想想分段树的每个节点应该需要包含什么样的信息，可以想象得出，它应该包含某个区间里的数的某种信息。
我们在之前介绍分段树知识点的时候，每个节点记录的区间是数组下标所形成的区间，然而对于这道题来说，因为我们要统计的是比某个数还要小的数的总和，如果我们把分段的区间设计成按照数值的大小来划分，并记录下在这个区间中的数的总和的话，那么我就能快速地知道比当前数还要小的数有多少个了。
如果你还是一头雾水，我们来看看具体是如何实现的。
首先，让我们从分段树的根节点开始，根节点记录的是数组里最小值到最大值之间的所有元素的总和，然后分割根节点成左区间和右区间，不断地分割下去，最后我们的分段树成为这样的模样：
[1 - 6] (0)
/ \
[1 - 3] (0) [4 - 6] (0)
/ \ / \
[1 - 2] (0) [3] (0) [4 - 5] (0) [6] (0)
/ \ / \
[1] (0) [2] (0) [4] (0) [5] (0)
初始化的时候，每个节点记录的在此区间内的元素数量是 0，接下来我们从数组的最后一位开始往前遍历，每次遍历，判断这个数落在哪个区间，那么那个区间的数量加一。
当我们遇到 1 的时候，把它加入到分段树里，此时分段树里各个节点所统计的数量会发生一定的变化：
[1 - 6] (1)
/ \
[1 - 3] (1) [4 - 6] (0)
/ \ / \
[1 - 2] (1) [3] (0) [4 - 5] (0) [6] (0)
/ \ / \
[1] (1) [2] (0) [4] (0) [5] (0)
同时我们知道当前所遇到的最小值就是 1。
接下来我们来看看 6，当我们把 6 加入到分段树里时，分段树会发生如下变化：
[1 - 6] (2)
/ \
[1 - 3] (1) [4 - 6] (1)
/ \ / \
[1 - 2] (1) [3] (0) [4 - 5] (0) [6] (1)
/ \ / \
[1] (1) [2] (0) [4] (0) [5] (0)
在这个时候，让我们来求一下比 6 小的数有多少个？其实也就是查询一下分段树，从 1 到 5 之间有多少个数。
我们从根节点开始查询。由于所要查询的区间是 1 到 5，它无法包含根节点的区间 1 到 6，所以继续往下查询。我们来看左边，很明显，区间 1 到 3 被完全包含在 1 到 5 之间，我们把该节点所统计好的数返回。我们再看来右边，区间 1 到 5 跟区间 4 到 6 有交叉，继续往下看，区间 4 到 5 完全被包含在 1 到 5 之间，所以我们可以马上返回，并把统计的数量相加。
最后我们得出，在当前位置，在 6 的右边比 6 小的数只有一个。
我们通过这样的方法，每次把当前的数用分段树进行个数统计，然后再计算出比它小的数即可。算法复杂度是 O(nlogn)。
树状数组（Fenwick Tree / Binary Indexed Tree）
图片: https://uploader.shimo.im/f/c…
最后我们来看看树状数组。
树状数组也被称为 Binary Indexed Tree，同样的，为了了解树状数组，让我们通过一个问题来好好理解一下这个数据结构吧。
假设我们有一个数组 array[0 … n-1]，里面有 n 个元素，现在我们要经常对这个数组做两件事：
更新数组元素的数值
求数组前 k 个元素的总和（或者平均值）
乍一看，我们似乎可以运用分段树来求解，的确，分段树是可以帮助我们在 O(logn)的时间里更新和求解前 k 个元素的总和。但是，让我们仔细看看这个问题，问题只要求求解前 k 个元素的总和，并不要求任意一个区间，在这种情况下，我们可以借用树状数组了，它可以让我们同样在 O(logn)的时间里完成上述的操作。而且，相对于分段树的实现，树状数组显得更简单。
树状数组的数据结构有以下几个重要的基本特征：
它是利用数组来表示多叉树的结构，在这一点上和优先队列有些类似，只不过，优先队列是用数组来表示完全二叉树，而树状数组是多叉树。
树状数组的第一个元素是空节点。
如果节点 tree[y]是 tree[x]的父节点，那么需要满足如下条件
y = x – (x & (-x))
由于树状数组所解决的问题跟分段树有些类似，所以我们就不花篇幅进行问题的讨论了，LeetCode 上有很多经典的题目可以用树状数组来解决，比如 LeetCode 第 308 题，求一个动态变化的二维矩阵里，任意子矩阵里的数的总和。
结语
图片: https://uploader.shimo.im/f/k…
通过这节课的学习，我们了解到了一些高级的数据结构。
优先队列可以说是经常出现在考题里的，它的实现过程比较繁琐，但是很多编程语言里都有它的实现，所以在解决面试中的问题时，实行“拿来主义”即可。我还是会鼓励你自己练习实现一个优先队列，在实现它的过程中更好地去了解它的结构和特点。
图是被广泛运用的数据结构，很多涉及大数据的问题都得运用到图论的知识，比如在社交网络里，每个人可以用图的顶点表示，人与人直接的关系可以用图的边表示，在比如，在地图上，要求解从起始点到目的地，如何行驶会更快捷，就得需要运用图论里的最短路径算法。
前缀树出现在许多面试的难题当中，很多时候，你得自己实现一棵前缀树，这要求你能熟练地书写它的实现以及运用它。
分段树和树状数组的应用场合比较明确，在这节课里我们对一维的情况进行了探讨，如果问题变为在一幅图片当中修改像素的颜色，然后求解任意矩形区间的灰度平均值，那么可以考虑采用二维的分段树了。
力扣平台上，针对上面的这些高级数据结构都有丰富的题目，希望你能用功地学习。
内容摘取自《300 分钟搞定算法面试》
第 02 讲：高级数据结构
主讲人：苏勇，谷歌资深技术工程师