高級(jí)算法和數(shù)據(jù)結(jié)構(gòu)

第 1章　初識(shí)數(shù)據(jù)結(jié)構(gòu)　1
1.1　數(shù)據(jù)結(jié)構(gòu)　2
1.1.1　定義數(shù)據(jù)結(jié)構(gòu)　2
1.1.2　描述數(shù)據(jù)結(jié)構(gòu)　3
1.1.3　算法與數(shù)據(jù)結(jié)構(gòu)有區(qū)別嗎　4
1.2　設(shè)定目標(biāo)：閱讀本書(shū)后的期望　4
1.3　打包背包：數(shù)據(jù)結(jié)構(gòu)與現(xiàn)實(shí)世界的結(jié)合　5
1.3.1　抽象化問(wèn)題　5
1.3.2　尋找解決方案　6
1.3.3　拯救大家的算法　7
1.3.4　打破常規(guī)來(lái)思考問(wèn)題　8
1.3.5　完美的結(jié)局　9
1.4　小結(jié)　9
第 一部分　改進(jìn)基本數(shù)據(jù)結(jié)構(gòu)
第 2章　改進(jìn)優(yōu)先隊(duì)列：d叉堆　12
2.1　本章結(jié)構(gòu)　13
2.2　問(wèn)題：處理優(yōu)先級(jí)　13
2.3　已知解決方案：讓列表保持有序　15
2.4　描述數(shù)據(jù)結(jié)構(gòu)API：優(yōu)先隊(duì)列　15
2.4.1　使用優(yōu)先隊(duì)列　16
2.4.2　優(yōu)先級(jí)為何非常重要　17
2.5　具體數(shù)據(jù)結(jié)構(gòu)　17
2.5.1　性能比較　18
2.5.2　正確的具體數(shù)據(jù)結(jié)構(gòu)是什么　18
2.5.3　堆　18
2.5.4　優(yōu)先級(jí)、最小堆和最大堆　20
2.5.5　高級(jí)變體：d叉堆　21
2.6　如何實(shí)現(xiàn)堆　22
2.6.1　向上冒泡　22
2.6.2　向下推動(dòng)　25
2.6.3　插入　27
2.6.4　移除頂部元素　28
2.6.5　修改　30
2.6.6　處理重復(fù)優(yōu)先級(jí)　31
2.6.7　堆化　32
2.6.8　API之外的方法：包含　34
2.6.9　性能回顧　34
2.6.10　從偽代碼到實(shí)現(xiàn)　35
2.7　用例：找到最大的k個(gè)元素　35
2.7.1　選擇正確的數(shù)據(jù)結(jié)構(gòu)　36
2.7.2　正確地使用數(shù)據(jù)結(jié)構(gòu)　36
2.7.3　代碼寫(xiě)起來(lái)　36
2.8　更多的用例　37
2.8.1　圖中的最小距離：Dijkstra算法　37
2.8.2　更多的圖算法：Prim算法　37
2.8.3　數(shù)據(jù)壓縮：霍夫曼編碼　38
2.9　對(duì)分支因子進(jìn)行分析　41
2.9.1　是否需要d叉堆　41
2.9.2　運(yùn)行時(shí)間　42
2.9.3　尋找最佳分支因子　42
2.9.4　分支因子與內(nèi)存的關(guān)系　43
2.10　性能分析：尋找最佳分支因子　43
2.10.1　剖析　44
2.10.2　解釋結(jié)果　45
2.10.3　堆化的謎團(tuán)　49
2.10.4　選擇最佳分支因子　49
2.11　小結(jié)　50
第3章　樹(shù)堆：使用隨機(jī)化來(lái)平衡二叉搜索樹(shù)　52
3.1　問(wèn)題：多索引　53
3.2　解決方案：描述與API　53
3.3　樹(shù)堆　54
3.3.1　旋轉(zhuǎn)　57
3.3.2　一些設(shè)計(jì)問(wèn)題　60
3.3.3　實(shí)現(xiàn)搜索方法　61
3.3.4　插入　61
3.3.5　刪除　64
3.3.6　去頂、看頂以及修改　66
3.3.7　返回最小鍵和最大鍵　67
3.3.8　性能回顧　67
3.4　應(yīng)用：隨機(jī)樹(shù)堆　68
3.4.1　平衡樹(shù)　68
3.4.2　引入隨機(jī)化　70
3.4.3　隨機(jī)樹(shù)堆的應(yīng)用　71
3.5　性能分析和剖析　72
3.5.1　理論：期望高度　72
3.5.2　剖析高度　74
3.5.3　剖析運(yùn)行時(shí)間　76
3.5.4　剖析內(nèi)存使用情況　78
3.5.5　結(jié)論　78
3.6　小結(jié)　80
第4章　布隆過(guò)濾器：減少跟蹤內(nèi)容所需的內(nèi)存　81
4.1　字典問(wèn)題：跟蹤事物　82
4.2　實(shí)現(xiàn)字典的其他方法　83
4.3　描述數(shù)據(jù)結(jié)構(gòu)API：關(guān)聯(lián)數(shù)組　83
4.4　具體數(shù)據(jù)結(jié)構(gòu)　84
4.4.1　無(wú)序數(shù)組：快速插入，慢速搜索　84
4.4.2　有序數(shù)組和二分查找：慢插入，稍微快一些的搜索　85
4.4.3　哈希表：在不需要有序的情況下，具有平均常數(shù)時(shí)間的性能　86
4.4.4　二叉搜索樹(shù)：所有操作都是對(duì)數(shù)階的　86
4.4.5　布隆過(guò)濾器：與哈希表一樣快，但（由于一個(gè)缺陷而）更節(jié)省內(nèi)存　88
4.5　表面之下：布隆過(guò)濾器是如何工作的　88
4.6　實(shí)現(xiàn)　89
4.6.1　使用布隆過(guò)濾器　90
4.6.2　位的讀取和寫(xiě)入　91
4.6.3　找到鍵存儲(chǔ)的位置　92
4.6.4　生成哈希函數(shù)　93
4.6.5　構(gòu)造函數(shù)　93
4.6.6　查找鍵　94
4.6.7　存儲(chǔ)鍵　95
4.6.8　估計(jì)準(zhǔn)確率　96
4.7　應(yīng)用場(chǎng)景　97
4.7.1　緩存　97
4.7.2　路由　98
4.7.3　爬蟲(chóng)　98
4.7.4　I/O提取器　98
4.7.5　拼寫(xiě)檢查器　98
4.7.6　分布式數(shù)據(jù)庫(kù)和文件系統(tǒng)　99
4.8　為什么布隆過(guò)濾器是可行的　99
4.8.1　為什么沒(méi)有假陰性　100
4.8.2　為什么有假陽(yáng)性　100
4.8.3　作為隨機(jī)算法的布隆過(guò)濾器　101
4.9　性能分析　101
4.9.1　運(yùn)行時(shí)間　101
4.9.2　構(gòu)造函數(shù)　102
4.9.3　存儲(chǔ)元素　102
4.9.4　查找元素　102
4.10　估計(jì)布隆過(guò)濾器的精確度　102
4.11　改進(jìn)的變體　106
4.11.1　布隆表過(guò)濾器　106
4.11.2　組合布隆過(guò)濾器　106
4.11.3　分層布隆過(guò)濾器　106
4.11.4　壓縮布隆過(guò)濾器　107
4.11.5　可擴(kuò)展布隆過(guò)濾器　107
4.12　小結(jié)　108
第5章　不交集：次線性時(shí)間的處理過(guò)程　109
5.1　不同子集問(wèn)題　110
5.2　解決方案的論證　111
5.3　描述數(shù)據(jù)結(jié)構(gòu)API：不交集　112
5.4　簡(jiǎn)單解決方案　113
5.5　使用樹(shù)狀結(jié)構(gòu)　117
5.5.1　從鏈表轉(zhuǎn)移到樹(shù)　117
5.5.2　實(shí)現(xiàn)使用樹(shù)的版本　118
5.6　改進(jìn)運(yùn)行時(shí)間的啟發(fā)式算法　120
5.6.1　路徑壓縮　121
5.6.2　實(shí)現(xiàn)平衡性與路徑壓縮　122
5.7　應(yīng)用程序　124
5.7.1　圖：連通分量　124
5.7.2　圖：最小生成樹(shù)的Kruskal算法　124
5.7.3　聚類　125
5.7.4　合一　126
5.8　小結(jié)　126
第6章　trie與基數(shù)樹(shù)：高效的字符串搜索　127
6.1　拼寫(xiě)檢查　128
6.1.1　拼寫(xiě)檢查器的設(shè)計(jì)　128
6.1.2　壓縮是關(guān)鍵　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　搜索最長(zhǎng)前綴詞　140
6.2.6　返回匹配特定前綴的所有鍵　141
6.2.7　什么時(shí)候應(yīng)該使用trie　143
6.3　基數(shù)樹(shù)　144
6.3.1　節(jié)點(diǎn)和邊　146
6.3.2　搜索　148
6.3.3　插入　149
6.3.4　刪除　151
6.3.5　搜索最長(zhǎng)前綴詞　153
6.3.6　返回匹配特定前綴的所有鍵　153
6.4　應(yīng)用程序　154
6.4.1　拼寫(xiě)檢查器　154
6.4.2　字符串相似度　156
6.4.3　字符串排序　157
6.4.4　T9　157
6.4.5　自動(dòng)完成　158
6.5　小結(jié)　158
第7章　用例：LRU緩存　160
7.1　不要重復(fù)計(jì)算　160
7.2　第 一次嘗試：記住數(shù)據(jù)　163
7.2.1　描述與API　164
7.2.2　請(qǐng)保存新數(shù)據(jù)　164
7.2.3　處理異步調(diào)用　165
7.2.4　將緩存的值標(biāo)記為“正在加載”　166
7.3　內(nèi)存（真的）不夠　167
7.4　清除陳舊數(shù)據(jù)：LRU緩存　168
7.4.1　有時(shí)必須要重復(fù)解決問(wèn)題　169
7.4.2　時(shí)間排序　170
7.4.3　性能　174
7.5　當(dāng)新數(shù)據(jù)更有價(jià)值時(shí)：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　同步簡(jiǎn)介　180
7.7.1　（在Java中）解決并發(fā)問(wèn)題　182
7.7.2　鎖簡(jiǎn)介　183
7.7.3　獲取鎖　183
7.7.4　重入鎖　184
7.7.5　讀鎖　185
7.7.6　解決并發(fā)的其他方法　186
7.8　緩存應(yīng)用程序　186
7.9　小結(jié)　187
第二部分　多維查詢
第8章　最近鄰搜索　190
8.1　最近鄰搜索問(wèn)題　190
8.2　解決方案　191
8.2.1　第 一次嘗試　191
8.2.2　有時(shí)緩存并不是答案　191
8.2.3　簡(jiǎn)化事情以獲得靈感　192
8.2.4　謹(jǐn)慎選擇數(shù)據(jù)結(jié)構(gòu)　193
8.3　描述與API　194
8.4　遷移到k維空間　195
8.4.1　一維二分查找　196
8.4.2　遷移到更高維度　196
8.4.3　用數(shù)據(jù)結(jié)構(gòu)對(duì)二維空間進(jìn)行建?！?97
8.5　小結(jié)　198
第9章　k-d樹(shù)：索引多維數(shù)據(jù)　199
9.1　從結(jié)束的地方繼續(xù)　199
9.2　遷移到k維空間：循環(huán)遍歷
維度　199
9.2.1　構(gòu)造BST　201
9.2.2　不變量　204
9.2.3　保持平衡的重要性　204
9.3　方法　205
9.3.1　搜索　206
9.3.2　插入　208
9.3.3　平衡樹(shù)　209
9.3.4　刪除　212
9.3.5　最近鄰搜索　218
9.3.6　區(qū)域搜索　224
9.3.7　所有方法的回顧　227
9.4　限制與可能的改進(jìn)　228
9.5　小結(jié)　229
第 10章　相似性搜索樹(shù)：圖像檢索的近似
最近鄰搜索　230
10.1　從結(jié)束的地方繼續(xù)　230
10.1.1　一個(gè)新的（更復(fù)雜的）例子　231
10.1.2　克服k-d樹(shù)的缺陷　232
10.2　R樹(shù)　232
10.2.1　先退一步：B樹(shù)簡(jiǎn)介　232
10.2.2　由B樹(shù)到R樹(shù)　233
10.2.3　在R樹(shù)中插入點(diǎn)　236
10.2.4　搜索　237
10.3　SS樹(shù)　238
10.3.1　搜索　241
10.3.2　插入　244
10.3.3　插入：方差、均值與投影　249
10.3.4　插入：分裂節(jié)點(diǎn)　252
10.3.5　刪除　255
10.4　相似性搜索　259
10.4.1　最近鄰搜索　260
10.4.2　區(qū)域搜索　262
10.4.3　近似相似性搜索　263
10.5　SS+樹(shù)　265
10.5.1　SS樹(shù)會(huì)更好嗎　266
10.5.2　緩解超球體的限制　267
10.5.3　改進(jìn)拆分啟發(fā)式算法　267
10.5.4　減少重疊　268
10.6　小結(jié)　270
第 11章　最近鄰搜索的應(yīng)用　271
11.1　應(yīng)用程序：查找最近的樞紐　271
11.1.1　解決方案的初稿　272
11.1.2　天堂里的麻煩　273
11.2　中心化應(yīng)用程序　274
11.2.1　過(guò)濾點(diǎn)　274
11.2.2　復(fù)雜的決定　276
11.3　遷移到分布式應(yīng)用程序　278
11.3.1　處理HTTP通信的問(wèn)題　279
11.3.2　保持庫(kù)存同步　281
11.3.3　經(jīng)驗(yàn)教訓(xùn)　281
11.4　其他應(yīng)用程序　282
11.4.1　色彩還原　282
11.4.2　粒子的相互作用　283
11.4.3　多維數(shù)據(jù)庫(kù)查詢的優(yōu)化　285
11.4.4　聚類　287
11.5　小結(jié)　287
第 12章　聚類　288
12.1　聚類簡(jiǎn)介　289
12.1.1　機(jī)器學(xué)習(xí)的類型　289
12.1.2　聚類的類型　290
12.2　k均值算法　291
12.2.1　k均值算法的問(wèn)題　295
12.2.2　維度詛咒再次來(lái)襲　296
12.2.3　k均值算法的性能分析　297
12.2.4　用k-d樹(shù)來(lái)加快k均值算法　297
12.2.5　關(guān)于k均值算法的最后一些提示　300
12.3　DBSCAN算法　300
12.3.1　直接可達(dá)與密度可達(dá)　301
12.3.2　從定義到算法　302
12.3.3　實(shí)現(xiàn)　304
12.3.4　DBSCAN算法的優(yōu)缺點(diǎn)　305
12.4　OPTICS算法　307
12.4.1　定義　308
12.4.2　OPTICS算法的核心思想　308
12.4.3　從可達(dá)距離到聚類　311
12.4.4　分層聚類　314
12.4.5　性能分析和最終的考慮　318
12.5　評(píng)估聚類結(jié)果：評(píng)估指標(biāo)　318
12.6　小結(jié)　322
第 13章　并行聚類：MapReduce與樹(shù)冠聚類　323
13.1　并行化　323
13.1.1　并行計(jì)算與分布式計(jì)算　324
13.1.2　并行化k均值算法　325
13.1.3　樹(shù)冠聚類　325
13.1.4　應(yīng)用樹(shù)冠聚類　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　并行化樹(shù)冠聚類　337
13.3.2　使用樹(shù)冠聚類來(lái)進(jìn)行質(zhì)心的初始化　339
13.3.3　MapReduce版本的樹(shù)冠聚類　340
13.4　MapReduce版本的DBSCAN 算法　343
13.5　小結(jié)　348

第三部分　平面圖與最小交叉數(shù)
第 14章　圖簡(jiǎn)介：尋找距離最短的
路徑　350
14.1　定義　351
14.1.1　圖的實(shí)現(xiàn)　351
14.1.2　作為代數(shù)類型的圖　353
14.1.3　偽代碼　354
14.2　圖的屬性　354
14.2.1　無(wú)向　355
14.2.2　連通　355
14.2.3　無(wú)環(huán)　356
14.3　圖的遍歷：BFS與DFS　357
14.3.1　優(yōu)化配送路線　357
14.3.2　廣度優(yōu)先搜索　359
14.3.3　重建到目標(biāo)的路徑　361
14.3.4　深度優(yōu)先搜索　362
14.3.5　再次比較隊(duì)列與堆?！?64
14.3.6　投遞包裹的最佳路線　365
14.4　加權(quán)圖中的最短路徑：迪杰斯特拉 算法　365
14.4.1　與BFS算法的區(qū)別　366
14.4.2　實(shí)現(xiàn)　367
14.4.3　分析　368
14.4.4　投遞包裹的最佳路線　369
14.5　超越迪杰斯特拉算法：A*
算法　370
14.5.1　A*算法到底有多好　372
14.5.2　將啟發(fā)式函數(shù)作為平衡實(shí)時(shí)數(shù)據(jù)的一種方式　375
14.6　小結(jié)　376
第 15章　圖嵌入與平面性：繪制具有最少相交邊的圖　377
15.1　圖嵌入　378
15.1.1　一些基礎(chǔ)定義　379
15.1.2　完全圖與完全二分圖　380
15.2　平面圖　381
15.2.1　在實(shí)踐中使用庫(kù)拉托夫斯基定理　381
15.2.2　平面性測(cè)試　382
15.2.3　用于平面性測(cè)試的樸素算法　383
15.2.4　提高性能　386
15.2.5　高效的算法　388
15.3　非平面圖　389
15.3.1　找到交叉數(shù)　391
15.3.2　直線交叉數(shù)　392
15.4　邊的交叉點(diǎn)　393
15.4.1　直線線段　394
15.4.2　折線　397
15.4.3　貝塞爾曲線　397
15.4.4　二次貝塞爾曲線之間的交點(diǎn)　398
15.4.5　頂點(diǎn)與頂點(diǎn)相交以及邊與頂點(diǎn)相交　401
15.5　小結(jié)　402
第 16章　梯度下降：（不僅是）圖的優(yōu)化問(wèn)題　403
16.1　用于交叉數(shù)的啟發(fā)式算法　404
16.1.1　剛才提到啟發(fā)式了嗎　404
16.1.2　擴(kuò)展到曲線邊　408
16.2　優(yōu)化的工作原理　409
16.2.1　成本函數(shù)　410
16.2.2　階躍函數(shù)與局部最小值　412
16.2.3　優(yōu)化隨機(jī)抽樣算法　412
16.3　梯度下降　414
16.3.1　梯度下降中的數(shù)學(xué)描述　415
16.3.2　幾何解釋　416
16.3.3　什么時(shí)候可以應(yīng)用梯度下降　418
16.3.4　梯度下降的問(wèn)題　418
16.4　梯度下降的應(yīng)用　419
16.5　使用梯度下降進(jìn)行圖嵌入　422
16.5.1　另一種標(biāo)準(zhǔn)　423
16.5.2　實(shí)現(xiàn)　425
16.6　小結(jié)　426
第 17章　模擬退火：超越局部最小值的優(yōu)化　427
17.1　模擬退火　428
17.1.1　有時(shí)候需要先向上爬才能到達(dá)底部　429
17.1.2　實(shí)現(xiàn)　431
17.1.3　為什么模擬退火是有效的　432
17.1.4　短程與長(zhǎng)程的轉(zhuǎn)換　434
17.1.5　變體　435
17.1.6　模擬退火與梯度下降：應(yīng)該選擇哪一個(gè)呢　436
17.2　模擬退火與旅行推銷員　436
17.2.1　精確解與近似解　438
17.2.2　可視化成本　438
17.2.3　修剪域　440
17.2.4　狀態(tài)轉(zhuǎn)換　440
17.2.5　相鄰交換與隨機(jī)交換　443
17.2.6　TSP近似算法的應(yīng)用　444
17.3　模擬退火與圖嵌入　444
17.3.1　最小邊交叉　445
17.3.2　力導(dǎo)向繪制　446
17.4　小結(jié)　450
第 18章　遺傳算法：受生物學(xué)啟發(fā)的快速收斂?jī)?yōu)化　451
18.1　遺傳算法簡(jiǎn)介　451
18.1.1　來(lái)自大自然的靈感　453
18.1.2　染色體　456
18.1.3　種群　457
18.1.4　適應(yīng)度　458
18.1.5　自然選擇　459
18.1.6　選擇交配的個(gè)體　461
18.1.7　交叉操作　466
18.1.8　突變操作　468
18.1.9　遺傳算法模板　469
18.1.10　遺傳算法在什么時(shí)候效果最好　470
18.2　TSP　471
18.2.1　適應(yīng)度、染色體與初始化　471
18.2.2　突變操作　472
18.2.3　交叉操作　472
18.2.4　結(jié)果與參數(shù)調(diào)整　473
18.2.5　超越TSP：優(yōu)化整個(gè)車隊(duì)的路線　476
18.3　最小頂點(diǎn)覆蓋　477
18.3.1　頂點(diǎn)覆蓋的應(yīng)用　478
18.3.2　實(shí)現(xiàn)遺傳算法　478
18.4　遺傳算法的其他應(yīng)用　480
18.4.1　最大流問(wèn)題　480
18.4.2　蛋白質(zhì)折疊　481
18.4.3　超越遺傳算法　482
18.4.4　算法，超越本書(shū)　483
18.5　小結(jié)　483
附錄A　偽代碼快速指南　485
附錄B　大O符號(hào)　494
附錄C　核心數(shù)據(jù)結(jié)構(gòu)　500
附錄D　類似于優(yōu)先隊(duì)列的容器　511
附錄E　遞歸　514
附錄F　分類問(wèn)題與隨機(jī)算法的度量指標(biāo)　520