在本模块中，我们将讨论动态数组：一种在事先不知道需要多少元素的情况下使用数组的方法。在此，我们还将讨论摊销分析：一种确定操作序列中操作的摊销成本的方法。摊销分析通常用于分析算法的性能，当直接分析得出的结果不能令人满意时，摊销分析有助于证明算法实际上是高效的。摊销分析既用于动态数组分析，也将在本课程的最后用于分析 Splay 树。

在本模块开始时，我们将考虑优先级队列，优先级队列可用于高效调度计算机操作系统或现实生活中的作业、排序庞大的文件（这是任何大数据处理算法最重要的组成部分）以及高效计算图中的最短路径（这是我们将在下一门课程中介绍的主题）。因此，优先队列在许多编程语言中都有内置实现，包括 C++、Java 和 Python。我们将看到，这些实现都基于一个美丽的想法，即在数组中存储一棵完整的二叉树，只需几行代码就能实现所有优先级队列方法。然后，我们将切换到不相邻集合数据结构，这种结构用于动态图连接和图像处理等。我们将再次看到简单而自然的想法是如何实现既易于编码又非常高效的。完成本模块后，你将能够从头开始高效地实现这两种数据结构。

在本模块中，你将学习到非常强大且应用广泛的散列技术。它的应用包括编程语言的实现、文件系统、模式搜索、分布式键值存储等。你将学习如何实现数据结构，以存储和修改对象集以及从一类对象到另一类对象的映射。你会发现，简单的实现要么消耗大量内存，要么速度很慢，然后你将学习如何实现哈希表，它使用线性内存，平均工作速度为 O(1)！最后，你将了解散列函数如何用于现代分布式系统，以及如何用于优化 Dropbox、Google Drive 和 Yandex Disk 等服务的存储！

在本模块中，我们将学习二叉搜索树，这是一种在动态变化的有序集合上进行搜索的数据结构。你将了解完成这项任务的许多困难，以及克服这些困难的方法。要做到这一点，你需要学习二叉搜索树的基本结构，如何在不破坏这种结构的情况下插入和删除，以及如何确保树保持平衡。

在本模块中，我们将继续研究二叉搜索树。我们将研究一些非难应用。然后，我们将研究新型平衡搜索树--Splay 树。它们能动态地适应查询，在很多方面都是最优的。