高级算法和数据结构

封面

版权信息

版权

内容提要

推荐序

序

致谢

前言

为什么要选择本书

读者对象

本书的内容是如何组织的：路线图

关于代码

作者简介

本书封面简介

第1章 初识数据结构

1.1 数据结构

1.2 设定目标：阅读本书后的期望

1.3 打包背包：数据结构与现实世界的结合

1.4 小结

第一部分 改进基本数据结构

第2章 改进优先队列：d叉堆

2.1 本章结构

2.2 问题：处理优先级

2.3 已知解决方案：让列表保持有序

2.4 描述数据结构API：优先队列

2.5 具体数据结构

2.6 如何实现堆

2.7 用例：找到最大的k个元素

2.8 更多的用例

2.9 对分支因子进行分析

2.10 性能分析：寻找最佳分支因子

2.11 小结

第3章 树堆：使用随机化来平衡二叉搜索树

3.1 问题：多索引

3.2 解决方案：描述与API

3.3 树堆

3.4 应用：随机树堆

3.5 性能分析和剖析

3.6 小结

第4章 布隆过滤器：减少跟踪内容所需的内存

4.1 字典问题：跟踪事物

4.2 实现字典的其他方法

4.3 描述数据结构API：关联数组

4.4 具体数据结构

4.5 表面之下：布隆过滤器是如何工作的

4.6 实现

4.7 应用场景

4.8 为什么布隆过滤器是可行的

4.9 性能分析

4.10 估计布隆过滤器的精确度

4.11 改进的变体

4.12 小结

第5章 不交集：次线性时间的处理过程

5.1 不同子集问题

5.2 解决方案的论证

5.3 描述数据结构API：不交集

5.4 简单解决方案

5.5 使用树状结构

5.6 改进运行时间的启发式算法

5.7 应用程序

5.8 小结

第6章 trie与基数树：高效的字符串搜索

6.1 拼写检查

6.2 trie

6.3 基数树

6.4 应用程序

6.5 小结

第7章 用例：LRU缓存

7.1 不要重复计算

7.2 第一次尝试：记住数据

7.3 内存（真的）不够

7.4 清除陈旧数据：LRU缓存

7.5 当新数据更有价值时：LFU

7.6 如何使用缓存也同样重要

7.7 同步简介

7.8 缓存应用程序

7.9 小结

第二部分 多维查询

第8章 最近邻搜索

8.1 最近邻搜索问题

8.2 解决方案

8.3 描述与API

8.4 迁移到k维空间

8.5 小结

第9章 k-d树：索引多维数据

9.1 从结束的地方继续

9.2 迁移到k维空间：循环遍历维度

9.3 方法

9.4 限制与可能的改进

9.5 小结

第10章 相似性搜索树：图像检索的近似最近邻搜索

10.1 从结束的地方继续

10.2 R树

10.3 SS树

10.4 相似性搜索

10.5 SS+树

10.6 小结

第11章 最近邻搜索的应用

11.1 应用程序：查找最近的枢纽

11.2 中心化应用程序