高級算法和數據結構

第 1章　初識數據結構　1
1.1　數據結構　2
1.1.1　定義數據結構　2
1.1.2　描述數據結構　3
1.1.3　算法與數據結構有區(qū)別嗎　4
1.2　設定目標：閱讀本書后的期望　4
1.3　打包背包：數據結構與現實世界的結合　5
1.3.1　抽象化問題　5
1.3.2　尋找解決方案　6
1.3.3　拯救大家的算法　7
1.3.4　打破常規(guī)來思考問題　8
1.3.5　完美的結局　9
1.4　小結　9
第 一部分　改進基本數據結構
第 2章　改進優(yōu)先隊列：d叉堆　12
2.1　本章結構　13
2.2　問題：處理優(yōu)先級　13
2.3　已知解決方案：讓列表保持有序　15
2.4　描述數據結構API：優(yōu)先隊列　15
2.4.1　使用優(yōu)先隊列　16
2.4.2　優(yōu)先級為何非常重要　17
2.5　具體數據結構　17
2.5.1　性能比較　18
2.5.2　正確的具體數據結構是什么　18
2.5.3　堆　18
2.5.4　優(yōu)先級、最小堆和最大堆　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　處理重復優(yōu)先級　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　布隆過濾器：與哈希表一樣快，但（由于一個缺陷而）更節(jié)省內存　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　分布式數據庫和文件系統(tǒng)　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　改進運行時間的啟發(fā)式算法　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　節(jié)點和邊　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中）解決并發(fā)問題　182
7.7.2　鎖簡介　183
7.7.3　獲取鎖　183
7.7.4　重入鎖　184
7.7.5　讀鎖　185
7.7.6　解決并發(fā)的其他方法　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　用數據結構對二維空間進行建?！?97
8.5　小結　198
第9章　k-d樹：索引多維數據　199
9.1　從結束的地方繼續(xù)　199
9.2　遷移到k維空間：循環(huán)遍歷
維度　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　區(qū)域搜索　224
9.3.7　所有方法的回顧　227
9.4　限制與可能的改進　228
9.5　小結　229
第 10章　相似性搜索樹：圖像檢索的近似
最近鄰搜索　230
10.1　從結束的地方繼續(xù)　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　插入：分裂節(jié)點　252
10.3.5　刪除　255
10.4　相似性搜索　259
10.4.1　最近鄰搜索　260
10.4.2　區(qū)域搜索　262
10.4.3　近似相似性搜索　263
10.5　SS+樹　265
10.5.1　SS樹會更好嗎　266
10.5.2　緩解超球體的限制　267
10.5.3　改進拆分啟發(fā)式算法　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　多維數據庫查詢的優(yōu)化　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算法的優(yōu)缺點　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　無環(huán)　356
14.3　圖的遍歷：BFS與DFS　357
14.3.1　優(yōu)化配送路線　357
14.3.2　廣度優(yōu)先搜索　359
14.3.3　重建到目標的路徑　361
14.3.4　深度優(yōu)先搜索　362
14.3.5　再次比較隊列與堆?！?64
14.3.6　投遞包裹的最佳路線　365
14.4　加權圖中的最短路徑：迪杰斯特拉 算法　365
14.4.1　與BFS算法的區(qū)別　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　將啟發(fā)式函數作為平衡實時數據的一種方式　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章　梯度下降：（不僅是）圖的優(yōu)化問題　403
16.1　用于交叉數的啟發(fā)式算法　404
16.1.1　剛才提到啟發(fā)式了嗎　404
16.1.2　擴展到曲線邊　408
16.2　優(yōu)化的工作原理　409
16.2.1　成本函數　410
16.2.2　階躍函數與局部最小值　412
16.2.3　優(yōu)化隨機抽樣算法　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章　模擬退火：超越局部最小值的優(yōu)化　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　狀態(tài)轉換　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章　遺傳算法：受生物學啟發(fā)的快速收斂優(yōu)化　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：優(yōu)化整個車隊的路線　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　類似于優(yōu)先隊列的容器　511
附錄E　遞歸　514
附錄F　分類問題與隨機算法的度量指標　520