如何提升数据结构方面的算法能力？

谈及为什么需要花时间学算法，我至少可以列举出三个很好的理由。

(1)性能：选择正确的算法可以显著提升应用程序的速度。仅就搜索来说，用二分查找替 换线性搜索就能为我们帶来巨大的收益。

(2)安全性：如果你选用了错误的算法，攻击者就可以利用它使你的服务器、节点或应 用程序崩溃。比如哈希碰撞拒绝服务攻击，就利用了作为字典来存放POST 请求以提交参数 的哈希表，并使用有可能导致大量碰撞的序列来让这个哈希表退化，进而使整个服务器停止 响应。另一个关于安全性的有趣例子是，曾有黑客成功使用有缺陷的随机数生成器入侵在线 扑克网站。1

(3)设计代码的效率：如果有合适的构建模块可用来完成各种事情(特别是如果还能重用代码的话),你就能更快地实现代码的编写，而且会让代码更整洁。

推荐你阅读《高级算法和数据结构》这本书

那么,为什么推荐你阅读本书呢？一个很重要的原因就是，在本书中，我精挑细选地为你准备了一个具有战略意义的“高级算法库”,其中的算法能够帮助你改进代码，进而应对现代系 统面临的各种挑战。

此外，我试着用一种不同于普通教材的方法来介绍这些算法。虽然本书也会解释算法背后 的理论，但更侧重于给出使用这些算法的实际应用程序的相关背景信息，以及在什么时候应该 使用这些算法的建议。

在日常工作中，你通常要做的是处理某个大型软件(也可能是遗留软件)上的某个特定部 分。但是，在整个职业生涯中，你肯定会遇到需要设计大型软件的情况。到了那时，你就会用 上本书讨论的大部分内容了。我将尽可能地给出有关如何编写简洁且高效代码的建议，以帮助 你解决将来要面对的相关问题。

正是因为采用了这种新的方式来介绍算法，所以在每一章中，我都会列举有助于解决某些问题的数据结构。这是一本当你需要用以提高应用程序性能的建议时，可以随时参考的辅助性手册。

——摘自《高级算法和数据结构》前言部分

为什么要学习数据结构和算法?简单来说，想要成为更优秀的软件开发人员，学习数据结构和算法能让我们事半功倍。

你有没有听说过“马斯洛的锤子”(又称为“工具规律”)?这是一个通过观察得到的 假设，意味着只知道一种做事方式的人，想把这种方式运用到所有情况之下，而不关注情 况的差异性。

如果只有锤子这一个工具，那么容易把所有东西当作钉子。类似地，如果只知道可以对 列表进行排序，那么在向任务列表中添加新的任务或者选择下一个需要处理的任务时，通常 就会尝试对任务列表进行排序，而不会根据上下文来获得更高效的解决方案。

本书旨在为你提供更多用于解决问题的“工具”。我们将以计算机科学专业基础课通常都会 介绍的基本算法作为基础，向你介绍更高级的内容。

读完本书，你应该能够知道在什么情况下，可以使用特定的数据结构和(或)算法来提高 代码的性能。

本书各章会按照“提出问题→设计数据结构作为解决方案→实现解决方案并分析运行时间 和内存需求”这一结构来安排内容。

最后，附录部分涵盖了阅读本书所必须掌握的那些关键主题。附录不是基于示例来讲解的， 而是采用了与正文不同的内容组织方式。附录旨在向读者提供在开始阅读正文之前就应该熟悉的 各种知识的摘要，其中的大部分主题是基础算法课程中的内容。我们建议读者在阅读第2章之前 浏览一遍附录中的内容。

附录 A 介绍了用来描述算法的伪代码的各种符号。

附录B 提供了对大O 符号以及时间分析与空间分析的总结。

附录C 和附录D 给出了各种核心数据结构的摘要。这些数据结构是本书将要介绍的各种高 级数据结构的基础模块。

附录 E 解释了递归。递归是一种比较具有挑战性的编程技术，旨在对算法进行更明确、更 简洁的定义。当然，在采用递归时，我们需要对利弊进行权衡。

附录 F 给出了不同类型的随机算法的定义，包括蒙特卡罗算法、拉斯维加斯算法，还介绍 了各种分类问题和随机解决方案的评估指标。

详细目录

第 1章 初识数据结构 1
1．1 数据结构 2
1．1．1 定义数据结构 2
1．1．2 描述数据结构 3
1．1．3 算法与数据结构有区别吗 4
1．2 设定目标：阅读本书后的期望 4
1．3 打包背包：数据结构与现实世界的结合 5
1．3．1 抽象化问题 5
1．3．2 寻找解决方案 6
1．3．3 拯救大家的算法 7
1．3．4 打破常规来思考问题 8
1．3．5 完美的结局 9
1．4 小结 9
第 一部分 改进基本数据结构
第 2章 改进优先队列：d叉堆 12
2．1 本章结构 13
2．2 问题：处理优先级 13
2．3 已知解决方案：让列表保持有序 15
2．4 描述数据结构API：优先队列 15
2．4．1 使用优先队列 16
2．4．2 优先级为何非常重要 17
2．5 具体数据结构 17
2．5．1 性能比较 18
2．5．2 正确的具体数据结构是什么 18
2．5．3 堆 18
2．5．4 优先级、最小堆和最大堆 20
2．5．5 高级变体：d叉堆 21
2．6 如何实现堆 22
2．6．1 向上冒泡 22
2．6．2 向下推动 25
2．6．3 插入 27
2．6．4 移除顶部元素 28
2．6．5 修改 30
2．6．6 处理重复优先级 31
2．6．7 堆化 32
2．6．8 API之外的方法：包含 34
2．6．9 性能回顾 34
2．6．10 从伪代码到实现 35
2．7 用例：找到最大的k个元素 35
2．7．1 选择正确的数据结构 36
2．7．2 正确地使用数据结构 36
2．7．3 代码写起来 36
2．8 更多的用例 37
2．8．1 图中的最小距离：Dijkstra算法 37
2．8．2 更多的图算法：Prim算法 37
2．8．3 数据压缩：霍夫曼编码 38
2．9 对分支因子进行分析 41
2．9．1 是否需要d叉堆 41
2．9．2 运行时间 42
2．9．3 寻找最佳分支因子 42
2．9．4 分支因子与内存的关系 43
2．10 性能分析：寻找最佳分支因子 43
2．10．1 剖析 44
2．10．2 解释结果 45
2．10．3 堆化的谜团 49
2．10．4 选择最佳分支因子 49
2．11 小结 50
第3章 树堆：使用随机化来平衡二叉搜索树 52
3．1 问题：多索引 53
3．2 解决方案：描述与API 53
3．3 树堆 54
3．3．1 旋转 57
3．3．2 一些设计问题 60
3．3．3 实现搜索方法 61
3．3．4 插入 61
3．3．5 删除 64
3．3．6 去顶、看顶以及修改 66
3．3．7 返回最小键和最大键 67
3．3．8 性能回顾 67
3．4 应用：随机树堆 68
3．4．1 平衡树 68
3．4．2 引入随机化 70
3．4．3 随机树堆的应用 71
3．5 性能分析和剖析 72
3．5．1 理论：期望高度 72
3．5．2 剖析高度 74
3．5．3 剖析运行时间 76
3．5．4 剖析内存使用情况 78
3．5．5 结论 78
3．6 小结 80
第4章 布隆过滤器：减少跟踪内容所需的内存 81
4．1 字典问题：跟踪事物 82
4．2 实现字典的其他方法 83
4．3 描述数据结构API：关联数组 83
4．4 具体数据结构 84
4．4．1 无序数组：快速插入，慢速搜索 84
4．4．2 有序数组和二分查找：慢插入，稍微快一些的搜索 85
4．4．3 哈希表：在不需要有序的情况下，具有平均常数时间的性能 86
4．4．4 二叉搜索树：所有操作都是对数阶的 86
4．4．5 布隆过滤器：与哈希表一样快，但（由于一个缺陷而）更节省内存 88
4．5 表面之下：布隆过滤器是如何工作的 88
4．6 实现 89
4．6．1 使用布隆过滤器 90
4．6．2 位的读取和写入 91
4．6．3 找到键存储的位置 92
4．6．4 生成哈希函数 93
4．6．5 构造函数 93
4．6．6 查找键 94
4．6．7 存储键 95
4．6．8 估计准确率 96
4．7 应用场景 97
4．7．1 缓存 97
4．7．2 路由 98
4．7．3 爬虫 98
4．7．4 I O提取器 98
4．7．5 拼写检查器 98
4．7．6 分布式数据库和文件系统 99
4．8 为什么布隆过滤器是可行的 99
4．8．1 为什么没有假阴性 100
4．8．2 为什么有假阳性 100
4．8．3 作为随机算法的布隆过滤器 101
4．9 性能分析 101
4．9．1 运行时间 101
4．9．2 构造函数 102
4．9．3 存储元素 102
4．9．4 查找元素 102
4．10 估计布隆过滤器的精确度 102
4．11 改进的变体 106
4．11．1 布隆表过滤器 106
4．11．2 组合布隆过滤器 106
4．11．3 分层布隆过滤器 106
4．11．4 压缩布隆过滤器 107
4．11．5 可扩展布隆过滤器 107
4．12 小结 108
第5章 不交集：次线性时间的处理过程 109
5．1 不同子集问题 110
5．2 解决方案的论证 111
5．3 描述数据结构API：不交集 112
5．4 简单解决方案 113
5．5 使用树状结构 117
5．5．1 从链表转移到树 117
5．5．2 实现使用树的版本 118
5．6 改进运行时间的启发式算法 120
5．6．1 路径压缩 121
5．6．2 实现平衡性与路径压缩 122
5．7 应用程序 124
5．7．1 图：连通分量 124
5．7．2 图：最小生成树的Kruskal算法 124
5．7．3 聚类 125
5．7．4 合一 126
5．8 小结 126
第6章 trie与基数树：高效的字符串搜索 127
6．1 拼写检查 128
6．1．1 拼写检查器的设计 128
6．1．2 压缩是关键 129
6．1．3 描述与API 129
6．2 trie 130
6．2．1 为什么trie更好 132
6．2．2 搜索 134
6．2．3 插入 137
6．2．4 删除 139
6．2．5 搜索最长前缀词 140
6．2．6 返回匹配特定前缀的所有键 141
6．2．7 什么时候应该使用trie 143
6．3 基数树 144
6．3．1 节点和边 146
6．3．2 搜索 148
6．3．3 插入 149
6．3．4 删除 151
6．3．5 搜索最长前缀词 153
6．3．6 返回匹配特定前缀的所有键 153
6．4 应用程序 154
6．4．1 拼写检查器 154
6．4．2 字符串相似度 156
6．4．3 字符串排序 157
6．4．4 T9 157
6．4．5 自动完成 158
6．5 小结 158
第7章 用例：LRU缓存 160
7．1 不要重复计算 160
7．2 第 一次尝试：记住数据 163
7．2．1 描述与API 164
7．2．2 请保存新数据 164
7．2．3 处理异步调用 165
7．2．4 将缓存的值标记为“正在加载” 166
7．3 内存（真的）不够 167
7．4 清除陈旧数据：LRU缓存 168
7．4．1 有时必须要重复解决问题 169
7．4．2 时间排序 170
7．4．3 性能 174
7．5 当新数据更有价值时：LFU 175
7．5．1 如何选择缓存的清除策略 176
7．5．2 LFU缓存有什么不同 176
7．5．3 性能 178
7．5．4 LFU缓存的不足 178
7．6 如何使用缓存也同样重要 179
7．7 同步简介 180
7．7．1 （在Java中）解决并发问题 182
7．7．2 锁简介 183
7．7．3 获取锁 183
7．7．4 重入锁 184
7．7．5 读锁 185
7．7．6 解决并发的其他方法 186
7．8 缓存应用程序 186
7．9 小结 187
第二部分 多维查询
第8章 最近邻搜索 190
8．1 最近邻搜索问题 190
8．2 解决方案 191
8．2．1 第 一次尝试 191
8．2．2 有时缓存并不是答案 191
8．2．3 简化事情以获得灵感 192
8．2．4 谨慎选择数据结构 193
8．3 描述与API 194
8．4 迁移到k维空间 195
8．4．1 一维二分查找 196
8．4．2 迁移到更高维度 196
8．4．3 用数据结构对二维空间进行建模 197
8．5 小结 198
第9章 k-d树：索引多维数据 199
9．1 从结束的地方继续 199
9．2 迁移到k维空间：循环遍历
维度 199
9．2．1 构造BST 201
9．2．2 不变量 204
9．2．3 保持平衡的重要性 204
9．3 方法 205
9．3．1 搜索 206
9．3．2 插入 208
9．3．3 平衡树 209
9．3．4 删除 212
9．3．5 最近邻搜索 218
9．3．6 区域搜索 224
9．3．7 所有方法的回顾 227
9．4 限制与可能的改进 228
9．5 小结 229
第 10章 相似性搜索树：图像检索的近似
最近邻搜索 230
10．1 从结束的地方继续 230
10．1．1 一个新的（更复杂的）例子 231
10．1．2 克服k-d树的缺陷 232
10．2 R树 232
10．2．1 先退一步：B树简介 232
10．2．2 由B树到R树 233
10．2．3 在R树中插入点 236
10．2．4 搜索 237
10．3 SS树 238
10．3．1 搜索 241
10．3．2 插入 244
10．3．3 插入：方差、均值与投影 249
10．3．4 插入：分裂节点 252
10．3．5 删除 255
10．4 相似性搜索 259
10．4．1 最近邻搜索 260
10．4．2 区域搜索 262
10．4．3 近似相似性搜索 263
10．5 SS+树 265
10．5．1 SS树会更好吗 266
10．5．2 缓解超球体的限制 267
10．5．3 改进拆分启发式算法 267
10．5．4 减少重叠 268
10．6 小结 270
第 11章 最近邻搜索的应用 271
11．1 应用程序：查找最近的枢纽 271
11．1．1 解决方案的初稿 272
11．1．2 天堂里的麻烦 273
11．2 中心化应用程序 274
11．2．1 过滤点 274
11．2．2 复杂的决定 276
11．3 迁移到分布式应用程序 278
11．3．1 处理HTTP通信的问题 279
11．3．2 保持库存同步 281
11．3．3 经验教训 281
11．4 其他应用程序 282
11．4．1 色彩还原 282
11．4．2 粒子的相互作用 283
11．4．3 多维数据库查询的优化 285
11．4．4 聚类 287
11．5 小结 287
第 12章 聚类 288
12．1 聚类简介 289
12．1．1 机器学习的类型 289
12．1．2 聚类的类型 290
12．2 k均值算法 291
12．2．1 k均值算法的问题 295
12．2．2 维度诅咒再次来袭 296
12．2．3 k均值算法的性能分析 297
12．2．4 用k-d树来加快k均值算法 297
12．2．5 关于k均值算法的最后一些提示 300
12．3 DBSCAN算法 300
12．3．1 直接可达与密度可达 301
12．3．2 从定义到算法 302
12．3．3 实现 304
12．3．4 DBSCAN算法的优缺点 305
12．4 OPTICS算法 307
12．4．1 定义 308
12．4．2 OPTICS算法的核心思想 308
12．4．3 从可达距离到聚类 311
12．4．4 分层聚类 314
12．4．5 性能分析和最终的考虑 318
12．5 评估聚类结果：评估指标 318
12．6 小结 322
第 13章 并行聚类：MapReduce与树冠聚类 323
13．1 并行化 323
13．1．1 并行计算与分布式计算 324
13．1．2 并行化k均值算法 325
13．1．3 树冠聚类 325
13．1．4 应用树冠聚类 327
13．2 MapReduce 328
13．2．1 MapReduce是如何工作的 328
13．2．2 先映射，后归约 331
13．2．3 表面之下，还有更多 334
13．3 MapReduce版本的k均值算法 334
13．3．1 并行化树冠聚类 337
13．3．2 使用树冠聚类来进行质心的初始化 339
13．3．3 MapReduce版本的树冠聚类 340
13．4 MapReduce版本的DBSCAN 算法 343
13．5 小结 348

第三部分 平面图与最小交叉数

第 14章 图简介：寻找距离最短的

路径 350

14．1 定义 351

14．1．1 图的实现 351

14．1．2 作为代数类型的图 353

14．1．3 伪代码 354

14．2 图的属性 354

14．2．1 无向 355

14．2．2 连通 355

14．2．3 无环 356

14．3 图的遍历：BFS与DFS 357

14．3．1 优化配送路线 357

14．3．2 广度优先搜索 359

14．3．3 重建到目标的路径 361

14．3．4 深度优先搜索 362

14．3．5 再次比较队列与堆栈 364

14．3．6 投递包裹的最佳路线 365

14．4 加权图中的最短路径：迪杰斯特拉 算法 365

14．4．1 与BFS算法的区别 366

14．4．2 实现 367

14．4．3 分析 368

14．4．4 投递包裹的最佳路线 369

14．5 超越迪杰斯特拉算法：A*

算法 370

14．5．1 A*算法到底有多好 372

14．5．2 将启发式函数作为平衡实时数据的一种方式 375

14．6 小结 376

第 15章 图嵌入与平面性：绘制具有最少相交边的图 377

15．1 图嵌入 378

15．1．1 一些基础定义 379

15．1．2 完全图与完全二分图 380

15．2 平面图 381

15．2．1 在实践中使用库拉托夫斯基定理 381

15．2．2 平面性测试 382

15．2．3 用于平面性测试的朴素算法 383

15．2．4 提高性能 386

15．2．5 高效的算法 388

15．3 非平面图 389

15．3．1 找到交叉数 391

15．3．2 直线交叉数 392

15．4 边的交叉点 393

15．4．1 直线线段 394

15．4．2 折线 397

15．4．3 贝塞尔曲线 397

15．4．4 二次贝塞尔曲线之间的交点 398

15．4．5 顶点与顶点相交以及边与顶点相交 401

15．5 小结 402

第 16章 梯度下降：（不仅是）图的优化问题 403

16．1 用于交叉数的启发式算法 404

16．1．1 刚才提到启发式了吗 404

16．1．2 扩展到曲线边 408

16．2 优化的工作原理 409

16．2．1 成本函数 410

16．2．2 阶跃函数与局部最小值 412

16．2．3 优化随机抽样算法 412

16．3 梯度下降 414

16．3．1 梯度下降中的数学描述 415

16．3．2 几何解释 416

16．3．3 什么时候可以应用梯度下降 418

16．3．4 梯度下降的问题 418

16．4 梯度下降的应用 419

16．5 使用梯度下降进行图嵌入 422

16．5．1 另一种标准 423

16．5．2 实现 425

16．6 小结 426

第 17章 模拟退火：超越局部最小值的优化 427

17．1 模拟退火 428

17．1．1 有时候需要先向上爬才能到达底部 429

17．1．2 实现 431

17．1．3 为什么模拟退火是有效的 432

17．1．4 短程与长程的转换 434

17．1．5 变体 435

17．1．6 模拟退火与梯度下降：应该选择哪一个呢 436

17．2 模拟退火与旅行推销员 436

17．2．1 精确解与近似解 438

17．2．2 可视化成本 438

17．2．3 修剪域 440

17．2．4 状态转换 440

17．2．5 相邻交换与随机交换 443

17．2．6 TSP近似算法的应用 444

17．3 模拟退火与图嵌入 444

17．3．1 最小边交叉 445

17．3．2 力导向绘制 446

17．4 小结 450

第 18章 遗传算法：受生物学启发的快速收敛优化 451

18．1 遗传算法简介 451

18．1．1 来自大自然的灵感 453

18．1．2 染色体 456

18．1．3 种群 457

18．1．4 适应度 458

18．1．5 自然选择 459

18．1．6 选择交配的个体 461

18．1．7 交叉操作 466

18．1．8 突变操作 468

18．1．9 遗传算法模板 469

18．1．10 遗传算法在什么时候效果最好 470

18．2 TSP 471

18．2．1 适应度、染色体与初始化 471

18．2．2 突变操作 472

18．2．3 交叉操作 472

18．2．4 结果与参数调整 473

18．2．5 超越TSP：优化整个车队的路线 476

18．3 最小顶点覆盖 477

18．3．1 顶点覆盖的应用 478

18．3．2 实现遗传算法 478

18．4 遗传算法的其他应用 480

18．4．1 最大流问题 480

18．4．2 蛋白质折叠 481

18．4．3 超越遗传算法 482

18．4．4 算法，超越本书 483

18．5 小结 483

附录A 伪代码快速指南 485

附录B 大O符号 494

附录C 核心数据结构 500

附录D 类似于优先队列的容器 511

附录E 递归 514

附录F 分类问题与随机算法的度量指标 520