第 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.8API之外的方法：包含34

2.6.9性能回顧34

2.6.10從偽代碼到實現35

2.7用例：找到最大素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解決方案：描述與API53

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.4I/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描述與API129

6.2trie130

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什麼時候應該使用trie143

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.4T9157

6.4.5自動完成158

6.5小結158

第7章用例：LRU緩存160

7.1不要重復計算160

7.2第 一次嘗試：記住數據163

7.2.1描述與API164

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當新數據更有價值時：LFU175

7.5.1如何選擇緩存的清除策略176

7.5.2LFU緩存有什麼不同176

7.5.3性能178

7.5.4LFU緩存的不足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描述與API194

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構造BST201

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.2R樹232

10.2.1先退一步：B樹簡介232

10.2.2由B樹到R樹233

10.2.3在R樹中插入點236

10.2.4搜索237

10.3SS樹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.5SS 樹265

10.5.1SS樹會更好嗎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.2k均值算法291

12.2.1k均值算法的問題295

12.2.2維度詛咒再次來襲296

12.2.3k均值算法的性能分析297

12.2.4用k-d樹來加快k均值算法297

12.2.5關於k均值算法的最後一些提示300

12.3DBSCAN算法300

12.3.1直接可達與密度可達301

12.3.2從定義到算法302

12.3.3實現304

12.3.4DBSCAN算法的優缺點305

12.4OPTICS算法307

12.4.1定義308

12.4.2OPTICS算法的核心思想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.2MapReduce328

13.2.1MapReduce是如何工作的328

13.2.2先映射，後歸約331

13.2.3表面之下，還有更多334

13.3MapReduce版本的k均值算法334

13.3.1並行化樹冠聚類337

13.3.2使用樹冠聚類來進行質心的初始化339

13.3.3MapReduce版本的樹冠聚類340

13.4MapReduce版本的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與DFS357

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.1A*算法到底有多好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.6TSP近似算法的應用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.2TSP471

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