然而，仅仅掌握好它们不足以应付大厂的算法面试的。为了达到对时间和空间复杂度的理想要求，本节课探究高级数据结构，它们的实现要比那些常用的数据结构要复杂得多。其中重点介绍：
- 优先队列
- 图
- 前缀树
- 线段树
- 树状数组
掌握好高级数据结构的性质以及所适用的场合，在分析问题的时候回归本质，很多题目都能迎刃而解。
优先队列（Priority Queue）
特点
能保证每次取出的元素都是队列中优先级别最高的。优先级别可以是自定义的，例如，数据的数值越大，优先级越高；或者数据的数值越小，优先级越高。优先级别甚至可以通过各种复杂的计算得到。
应用场景
从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分乃至全部的数据。
举例：任意一个数组，找出前 k 大的数。
解法 1：先对这个数组进行排序，然后依次输出前 k 大的数，复杂度将会是 O(nlogn)，其中，n 是数组的元素个数。这是一种直接的办法。
解法 2：使用优先队列，复杂度优化成 O(k + nlogk)。
当数据量很大（即 n 很大），而 k 相对较小的时候，显然，利用优先队列能有效地降低算法复杂度。因为要找出前 k 大的数，并不需要对所有的数进行排序。
实现
优先队列的本质是一个二叉堆结构。堆在英文里叫 Binary Heap，它是利用一个数组结构来实现的完全二叉树。换句话说，优先队列的本质是一个数组，数组里的每个元素既有可能是其他元素的父节点，也有可能是其他元素的子节点，而且，每个父节点只能有两个子节点，很像一棵二叉树的结构。
牢记下面优先队列有三个重要的性质。
1. 数组里的第一个元素 array[0] 拥有最高的优先级别。
2. 给定一个下标 i，那么对于元素 array[i] 而言：
- 它的父节点所对应的元素下标是 (i-1)/2
- 它的左孩子所对应的元素下标是 2×i + 1
- 它的右孩子所对应的元素下标是 2×i + 2
3. 数组里每个元素的优先级别都要高于它两个孩子的优先级别。
优先队列最基本的操作有两个。
1. 向上筛选（sift up / bubble up）
当有新的数据加入到优先队列中，新的数据首先被放置在二叉堆的底部。
不断进行向上筛选的操作，即如果发现该数据的优先级别比父节点的优先级别还要高，那么就和父节点的元素相互交换，再接着往上进行比较，直到无法再继续交换为止。
时间复杂度：由于二叉堆是一棵完全二叉树，并假设堆的大小为 k，因此整个过程其实就是沿着树的高度往上爬，所以只需要 O(logk) 的时间。
2. 向下筛选（sift down / bubble down）
当堆顶的元素被取出时，要更新堆顶的元素来作为下一次按照优先级顺序被取出的对象，需要将堆底部的元素放置到堆顶，然后不断地对它执行向下筛选的操作。
将该元素和它的两个孩子节点对比优先级，如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换，然后反复进行下去，直到无法继续交换为止。
时间复杂度：整个过程就是沿着树的高度往下爬，所以时间复杂度也是 O(logk)。
因此，无论是添加新的数据还是取出堆顶的元素，都需要 O(logk) 的时间。
初始化
优先队列的初始化是一个最重要的时间复杂度，是分析运用优先队列性能时必不可少的，也是经常容易弄错的地方。
举例：有 n 个数据，需要创建一个大小为 n 的堆。
误区：每当把一个数据加入到堆里，都要对其执行向上筛选的操作，这样一来就是 O(nlogn)。
解法：在创建这个堆的过程中，二叉树的大小是从 1 逐渐增长到 n 的，所以整个算法的复杂度经过推导，最终的结果是 O(n)。
注意：算法面试中是不要求推导的，你只需要记住，初始化一个大小为 n 的堆，所需要的时间是 O(n) 即可。
例题分析
LeetCode 第 347 题：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
说明：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(nlogn) ，n 是数组的大小
示例：car，car，book，desk，desk，desk
解题思路
这道题的输入是一个字符串数组，数组里的元素可能会重复一次甚至多次，要求按顺序输出前 k 个出现次数最多的字符串。
解这类求"前 k 个"的题目，关键是看如何定义优先级以及优先队列中元素的数据结构。
- 题目中有”前 k 个“这样的字眼，应该很自然地联想到优先队列。
- 优先级别可以由字符串出现的次数来决定，出现的次数越多，优先级别越高，反之越低。
- 统计词频的最佳数据结构就是哈希表（Hash Map），利用一个哈希表，就能快速地知道每个单词出现的次数。
- 将单词和其出现的次数作为一个新的对象来构建一个优先队列，那么这个问题就很轻而易举地解决了。
建议：这道题是利用优先队列处理问题的典型，建议好好练习。
Desk (3)
/ \
car(2) book(1)
图（Graph）
基本知识点
- 图可以说是所有数据结构里面知识点最丰富的一个，最基本的知识点如下。
- 阶（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 里边有许多关于图论的算法题，而且都是非常经典的题目，可以通过练习解题来熟练掌握必备知识。
