然而，仅仅掌握好它们不足以应付大厂的算法面试的。为了达到对时间和空间复杂度的理想要求，本节课探究高级数据结构，它们的实现要比那些常用的数据结构要复杂得多。其中重点介绍：

• 优先队列

• 图

• 前缀树

• 线段树

• 树状数组

掌握好高级数据结构的性质以及所适用的场合，在分析问题的时候回归本质，很多题目都能迎刃而解。

优先队列（Priority Queue）

特点

能保证每次取出的元素都是队列中优先级别最高的。优先级别可以是自定义的，例如，数据的数值越大，优先级越高；或者数据的数值越小，优先级越高。优先级别甚至可以通过各种复杂的计算得到。

应用场景

从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分乃至全部的数据。

举例：任意一个数组，找出前 k 大的数。

解法 1：先对这个数组进行排序，然后依次输出前 k 大的数，复杂度将会是 O(nlogn)，其中，n 是数组的元素个数。这是一种直接的办法。

解法 2：使用优先队列，复杂度优化成 O(k + nlogk)。

当数据量很大（即 n 很大），而 k 相对较小的时候，显然，利用优先队列能有效地降低算法复杂度。因为要

文章来源: lansonli.blog.csdn.net，作者：Lansonli，版权归原作者所有，如需转载，请联系作者。

原文链接：lansonli.blog.csdn.net/article/details/102919462