目錄
- 1.各種表的對(duì)比
參考基本數(shù)據(jù)結(jié)構(gòu)ADT及其實(shí)現(xiàn)
1.1 三種表
1.2 表的兩種實(shí)現(xiàn)（數(shù)組宋距、鏈表）之間的對(duì)比
1.3 棧和隊(duì)列的應(yīng)用 - 2.有序數(shù)組的二分查找附鸽、查找樹（搜索樹）尝盼、跳躍表之間的關(guān)系
2.1 有序數(shù)組的二分查找、二叉搜索樹與跳躍表
參考查找樹（搜索樹）
??2.1.1 三者的本質(zhì)是一樣——快速索引中間元素
??2.1.2 來看看二叉搜索樹和跳躍表的定義
2.2 普通二叉搜索樹、伸展樹與各種平衡搜索樹
??2.2.1 普通二叉搜索樹——保證平均情況O(lgn)
??2.2.2 伸展樹——保證攤還代價(jià)為O(lgn)
??2.2.3 平衡搜索樹——帶有平衡條件的二叉搜索樹（使得樹高最壞情況下為O(lgn)）
2.3 紅黑樹丈氓、1-2-3確定性跳躍表與2-3-4樹及2-3樹
參考紅黑樹專題
??2.3.1 2-3樹
??2.3.2 2-3-4樹
??2.3.3 基于2-3樹的左傾紅黑樹
??2.3.4 基于2-3-4樹的左傾紅黑樹
??2.3.5 1-2-3確定性跳躍表與2-3-4樹
??參考隨機(jī)算法中的跳躍表
2.4 二叉搜索樹與B樹
參考查找樹（搜索樹）中的B樹 - 3.各種查找數(shù)據(jù)結(jié)構(gòu)的對(duì)比
3.1 對(duì)比
3.2 各種查找數(shù)據(jù)結(jié)構(gòu)的應(yīng)用
??3.2.1 紅黑樹的應(yīng)用
??3.2.2 B/B+樹的應(yīng)用
??3.2.3 Trie樹（字典樹）的應(yīng)用
??3.2.4 radix樹的應(yīng)用
??3.2.5 哈希算法的應(yīng)用 - 4.各種堆（優(yōu)先隊(duì)列）之間的對(duì)比
參考優(yōu)先隊(duì)列——堆
4.1 堆（優(yōu)先隊(duì)列）與搜索樹之間的對(duì)比
4.2 各種堆（優(yōu)先隊(duì)列）之間的對(duì)比
??4.2.1 二叉堆與d-堆（數(shù)組實(shí)現(xiàn)）——合并困難
??4.2.2 可合并堆——鏈?zhǔn)浇Y(jié)構(gòu)
??4.2.3 van Emde Boas樹——特定條件下突破比較類型堆的限制
??4.2.4 配對(duì)堆——結(jié)構(gòu)限制特別少的堆（簡(jiǎn)單性造就了高效率：合并Θ(1)软免，DecreaseKey為O(lgn)）
4.3 堆（優(yōu)先隊(duì)列）的應(yīng)用
??4.3.1 帶寬管理（網(wǎng)絡(luò)路由器）
??4.3.2 離散事件模擬
??4.3.3 Dijkstra算法
??4.3.4 Huffman編碼
??4.3.5 Best-first搜索算法（比如A*搜索算法）
??4.3.6 Prim算法
??4.3.7 ROAM triangulation algorithm
1.各種表的對(duì)比
1.1 三種表
- 普通表
- 棧是LIFO表（后進(jìn)先出）
- 隊(duì)列是FIFO表（先進(jìn)先出）
1.2 表的兩種實(shí)現(xiàn)（數(shù)組宫纬、鏈表）之間的對(duì)比
核心本質(zhì)只有一條：就是數(shù)組需要連續(xù)存放，所以需要事先劃定一塊連續(xù)空間大谢蚋堋（提前占有哪怔，以防被占用），這才導(dǎo)致了數(shù)組鏈表的所有區(qū)別向抢。
- 存放：數(shù)組在連續(xù)存放的认境，鏈表不需要
因?yàn)榇娣诺倪@個(gè)特性導(dǎo)致了下面的區(qū)別：
a. 訪問：數(shù)組可以常數(shù)時(shí)間訪問第k個(gè)元素，鏈表需要從前向后遍歷
b. 插入和刪除：數(shù)組需要移動(dòng)很多元素挟鸠，鏈表常數(shù)時(shí)間即可完成 - 數(shù)組一般需要確定大小叉信，鏈表是動(dòng)態(tài)分配分配
因此數(shù)組一般是從棧中分配空間（廣義上的數(shù)組，也可以從堆中獲取艘希，數(shù)組本質(zhì)上只不過是指針的語法糖衣）硼身，鏈表是從堆中分配空間
1.3 棧和隊(duì)列的應(yīng)用
- 棧的對(duì)用
平衡符號(hào)（括號(hào)的成對(duì)匹配）
后綴表達(dá)式
中綴到后綴的轉(zhuǎn)換
函數(shù)調(diào)用 - 隊(duì)列的應(yīng)用
排隊(duì)論
任務(wù)隊(duì)列
在圖論中有大量應(yīng)用
消息隊(duì)列
linux內(nèi)核進(jìn)程隊(duì)列（按優(yōu)先級(jí)排隊(duì)）
2.有序數(shù)組的二分查找、查找樹（搜索樹）覆享、跳躍表之間的關(guān)系
2.1 有序數(shù)組的二分查找佳遂、二叉搜索樹與跳躍表
2.1.1 三者的本質(zhì)是一樣——快速索引中間元素
- 對(duì)于一個(gè)靜態(tài)表（不允許插入），對(duì)其在初始化是就排序是值得的撒顿。
但是現(xiàn)代應(yīng)用需要同時(shí)能夠支持高效的查找和插入兩種操作的數(shù)據(jù)結(jié)構(gòu)（符號(hào)表）丑罪。 - 怎樣找到這種數(shù)據(jù)結(jié)構(gòu)（符號(hào)表）？
1）高效插入凤壁，需要鏈?zhǔn)浇Y(jié)構(gòu)
2）二分查找能夠快速進(jìn)行查找（二分查找的高效來自于能夠快速通過索引取得任何子數(shù)組的中間元素）
因此將二者結(jié)合起來吩屹，就是二叉查找樹和跳躍表。
2.1.2 來看看二叉搜索樹和跳躍表的定義
-
（直接將中間元素放在根節(jié)點(diǎn)）二叉搜索樹中的關(guān)鍵字總是以滿足二叉搜索樹性質(zhì)的方式來存儲(chǔ)：
設(shè)x是二叉搜索樹中的一個(gè)結(jié)點(diǎn)拧抖。如果y是x左子樹中的一個(gè)結(jié)點(diǎn)煤搜，那么y.key <= x.key。如果y是x右子樹中的一個(gè)結(jié)點(diǎn)唧席，那么y.key >= x.key擦盾。
-
（結(jié)點(diǎn)帶有指向中間元素的索引）
1）k階結(jié)點(diǎn)：帶有k個(gè)指針的結(jié)點(diǎn)嘲驾。任意k階上的第i階（i <= k）指針指向的下一個(gè)結(jié)點(diǎn)至少具有i階。
2）大約有一半的結(jié)點(diǎn)是1階厌衙；大約1/4的結(jié)點(diǎn)是2階距淫；一般的，大約1/2^i的結(jié)點(diǎn)是i階結(jié)點(diǎn)婶希。按照這個(gè)概率分布隨機(jī)選擇結(jié)點(diǎn)的階數(shù)榕暇。最容易的方法是拋一枚硬幣直到正面出現(xiàn)并把拋硬幣的總次數(shù)作為該節(jié)點(diǎn)的階數(shù)。
2.2 普通二叉搜索樹喻杈、伸展樹與各種平衡搜索樹
2.2.1 普通二叉搜索樹——保證平均情況O(lgn)
- 高度為h的二叉搜索樹彤枢，查找、插入和刪除運(yùn)行時(shí)間均為O(h)筒饰。
二叉搜索樹（節(jié)點(diǎn)數(shù)為n）最壞情況下缴啡，高度h = n，隨機(jī)構(gòu)造的二叉搜索樹的期望高度為O(lgn)瓷们。
2.2.2 伸展樹——保證攤還代價(jià)為O(lgn)
- 當(dāng)一個(gè)結(jié)點(diǎn)被訪問后业栅，它就要經(jīng)過一系列AVL樹的旋轉(zhuǎn)被放到根上。
因?yàn)樵S多應(yīng)用中谬晕，當(dāng)一個(gè)結(jié)點(diǎn)被訪問碘裕，它就很可能不久再次被訪問到，如果碰到O(N)的結(jié)點(diǎn)攒钳，沒有被移動(dòng)帮孔，那么很難得到O(lgN)攤還時(shí)間。 - 保證從空樹開始任意連續(xù)M次對(duì)數(shù)的操作最多花費(fèi)O(MlogN)不撑。雖然這種保證不排除任意一次操作花費(fèi)O(N)時(shí)間文兢。一棵伸展樹每次操作的攤還代價(jià)是O(logN)。
2.2.3 平衡搜索樹——帶有平衡條件的二叉搜索樹（使得樹高最壞情況下為O(lgn)）
-
AVL（Adelson-Velskii和Landis）樹：一棵AVL樹是其每個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度最多差1的二叉查找樹焕檬。（空樹的高度定義為-1）
在高度為h的AVL樹中姆坚，最少節(jié)點(diǎn)數(shù)S(h)由S(h) = S(h-1) + S(h-2) + 1，由n >= S(h)实愚，可以得到h的最大界旷偿。
-
一棵紅黑樹是滿足下面紅黑性質(zhì)的二叉搜索樹（本質(zhì)上是基于2-3-4樹的紅黑樹）：
1）每個(gè)結(jié)點(diǎn)或是紅色的，或是黑色的
2）根節(jié)點(diǎn)是黑色的
3）每個(gè)葉節(jié)點(diǎn)NIL時(shí)黑色的（這條性質(zhì)可去掉）
4）如果一個(gè)結(jié)點(diǎn)是紅色的爆侣，則它的兩個(gè)子節(jié)點(diǎn)都是黑色的
5）對(duì)每個(gè)結(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡(jiǎn)單路徑上幢妄，均包含相同數(shù)目的黑色結(jié)點(diǎn)
紅黑樹確保沒有一條路徑會(huì)比其他路徑長(zhǎng)處2倍兔仰，因而近似于平衡的。（一條最長(zhǎng)的路徑是黑紅相間蕉鸳，一條最短的是全黑乎赴，但是黑色結(jié)點(diǎn)個(gè)數(shù)是相等的忍法。）
2.3 紅黑樹、1-2-3確定性跳躍表與2-3-4樹及2-3樹
2.3.1 2-3樹
- 2-3樹是一棵完美平衡的2-3查找樹榕吼，也即根節(jié)點(diǎn)到所有空鏈接都應(yīng)該是相同
-
2-3樹包含以下結(jié)點(diǎn)：
1）2-結(jié)點(diǎn)：含有一個(gè)健和兩條鏈接
2）3-結(jié)點(diǎn)：含有兩個(gè)鍵和三條鏈接
2.3.2 2-3-4樹
- 2-3-4樹是一棵完美平衡的2-3-4查找樹饿序，也即根節(jié)點(diǎn)到所有空鏈接都應(yīng)該是相同
-
2-3-4樹包含以下結(jié)點(diǎn)：
1）2-結(jié)點(diǎn)：含有一個(gè)健和兩條鏈接
2）3-結(jié)點(diǎn)：含有兩個(gè)鍵和三條鏈接
3）4-結(jié)點(diǎn)：含有三個(gè)鍵和四條鏈接
樹高：
- 最壞情況lgN（全是2-結(jié)點(diǎn)）
- 最好情況log4N = 1/2lgN（全是4-結(jié)點(diǎn)）
2.3.3 基于2-3樹的左傾紅黑樹
基于2-3樹的左傾紅黑樹是含有紅黑鏈接并滿足下列條件的二叉查找樹：
- 紅鏈接均為左鏈接
- 沒有任何一個(gè)結(jié)點(diǎn)同時(shí)和兩條紅鏈接相連
- 該樹是完美黑色平衡的，即任意空連接到根節(jié)點(diǎn)的路徑上黑鏈接數(shù)量相同羹蚣。
- 鏈接的顏色保存在鏈接的兒子結(jié)點(diǎn)中
2.3.4 基于2-3-4樹的左傾紅黑樹
-
基于2-3-4樹的左傾紅黑樹中3-結(jié)點(diǎn)和4-結(jié)點(diǎn)具有唯一的對(duì)應(yīng)：
-
如下是不允許：
不允許右傾
不允許上下連續(xù)兩個(gè)紅鏈接 -
因此基于2-3-4樹的左傾紅黑樹和2-3-4樹有唯一的一一對(duì)應(yīng)關(guān)系
2.3.5 1-2-3確定性跳躍表與2-3-4樹
- 鏈接：如果至少存在一個(gè)指針從一個(gè)元素指向另一個(gè)元素原探，則稱兩個(gè)元素是鏈接的
- 間隙容量：兩個(gè)在高度為h鏈接的元素間的間隙容量等于他們之間高度為h-1的元素個(gè)數(shù)
- 1-2-3確定性跳躍表：每一個(gè)間隙（除在頭和尾之間可能的零間隙外）的容量為1、2顽素、3咽弦。
2.4 二叉搜索樹與B樹
-
B樹的結(jié)點(diǎn)可以有很多孩子。B樹以一種自然的方式推廣了二叉搜索樹胁出。
如果B樹的一個(gè)內(nèi)部結(jié)點(diǎn)x包含x.n個(gè)關(guān)鍵字型型，那么結(jié)點(diǎn)x就有x.n+1個(gè)子域。結(jié)點(diǎn)x中的關(guān)鍵字就是分割點(diǎn)全蝶，它把結(jié)點(diǎn)x中所處理的關(guān)鍵字的屬性分割成x.n+1一個(gè)子域闹蒜，每一個(gè)子域由x的一個(gè)孩子處理。
一棵包含最小可能關(guān)鍵字的B樹：
3.各種查找數(shù)據(jù)結(jié)構(gòu)的對(duì)比
3.1 對(duì)比
3.2 各種查找數(shù)據(jù)結(jié)構(gòu)的應(yīng)用
3.2.1 紅黑樹的應(yīng)用
- STL中的map和set的實(shí)現(xiàn)
- 著名的linux進(jìn)程調(diào)度[Completely Fair Scheduler]抑淫，用紅黑樹管理進(jìn)程控制塊
- epoll在內(nèi)核中的實(shí)現(xiàn)绷落，用紅黑樹管理事件塊
- nginx中，用紅黑樹管理timer等
- Java的TreeMap實(shí)現(xiàn)
3.2.2 B/B+樹的應(yīng)用
- B和B+主要用在文件系統(tǒng)以及數(shù)據(jù)庫中做索引等丈冬，比如Mysql：B-Tree Index in MySql
3.2.3 Trie樹（字典樹）的應(yīng)用
- 用在統(tǒng)計(jì)和排序大量字符串嘱函，如自動(dòng)機(jī)
- trie 樹的一個(gè)典型應(yīng)用是前綴匹配，比如下面這個(gè)很常見的場(chǎng)景埂蕊，在我們輸入時(shí)往弓，搜索引擎會(huì)給予提示
- IP選路，也是前綴匹配蓄氧，一定程度會(huì)用到trie
3.2.4 radix樹的應(yīng)用
3.2.5 哈希算法的應(yīng)用
hash就是一個(gè)function函似，但不要太狹隘，函數(shù)的輸入不一定得是數(shù)字喉童，它還可以是其它所有的二進(jìn)制數(shù)據(jù)（字符串撇寞、文件等），但必須得有以下特點(diǎn)：
1）同一個(gè)輸入一定對(duì)應(yīng)著同一個(gè)輸出堂氯；
2）不同輸入的輸出可能會(huì)一樣蔑担；
下面通過兩個(gè)常見的使用場(chǎng)景解釋可能比較容易理解；
應(yīng)用場(chǎng)景一：構(gòu)建查找表比如在數(shù)據(jù)結(jié)構(gòu)中的hash表咽白，輸入是key啤握，簡(jiǎn)單的function如key/N，輸出是數(shù)組下標(biāo)晶框，但因?yàn)榈诙€(gè)特點(diǎn)排抬，不同key可能會(huì)得到相同的輸出懂从，所以在各類語言中的hashmap庫實(shí)現(xiàn)時(shí)，會(huì)針對(duì)的做相應(yīng)處理蹲蒲，比如從沖突的地方繼續(xù)做hash運(yùn)算番甩，直到不沖突為止等；
應(yīng)用場(chǎng)景二：數(shù)字簽名
本質(zhì)還是一樣届搁，利用hash 的function對(duì)輸入做運(yùn)算缘薛，這些運(yùn)算不局限于上述應(yīng)用的數(shù)字運(yùn)算，還可以有各類位運(yùn)算等咖祭，所以輸入也就不再局限于數(shù)字了掩宜，而是只要是二進(jìn)制數(shù)據(jù)就行，比如字符串么翰、文件等牺汤。雖然輸入、function浩嫌、輸出形式不一樣檐迟，上述的兩個(gè)特點(diǎn)還是成立的。除此之外码耐，為了保證簽名的要求追迟，hash function的設(shè)置者會(huì)針對(duì)性的研究function的實(shí)現(xiàn)方法，以獲得第三個(gè)特點(diǎn)：
3）已知輸出骚腥，不可反推得到輸入敦间。
4.各種堆（優(yōu)先隊(duì)列）之間的對(duì)比
4.1 堆（優(yōu)先隊(duì)列）與搜索樹之間的對(duì)比
1）（最大）堆的定義
優(yōu)先隊(duì)列是允許至少下列兩種操作的數(shù)據(jù)結(jié)構(gòu)：
- 1）Insert
- 2）DeleteMax 找出、返回和刪除優(yōu)先隊(duì)列中最大的元素
并且一般的實(shí)現(xiàn)都以最壞情形O(lgn)支持上面兩個(gè)操作束铭。
2）查找樹的定義
支持SEARCH(Find)廓块、MINIMUM(FindMin)、MAXIMUM(Find Max)契沫、PREDECESSOR带猴、SUCCESSOR、INSERT和DELETE等集合操作懈万。
3）對(duì)比
- 查找樹可以實(shí)現(xiàn)對(duì)的所有操作拴清，并且平衡查找樹可以實(shí)現(xiàn)最壞情形O(lgn)支持堆的操作（Insert、DeleteMax）
但是查找樹還提供很多其他堆不需要的操作 - 查找樹里面的元素是全部有序的会通，而堆只需要時(shí)刻能有效地找出最值口予，因此無需全部有序
因此堆的實(shí)現(xiàn)可以比查找樹更簡(jiǎn)單
4.2 各種堆（優(yōu)先隊(duì)列）之間的對(duì)比
4.2.1 二叉堆與d-堆（數(shù)組實(shí)現(xiàn)）——合并困難
1）二叉堆（數(shù)組實(shí)現(xiàn)）
- 二叉堆是一個(gè)數(shù)組，可以被看成一個(gè)近似的完全二叉樹涕侈。樹上的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)數(shù)組中的一個(gè)元素苹威。除了最底層外，該樹是完全充滿的驾凶。而且是從左向右填充牙甫。
-
對(duì)于最大堆而言：最大元應(yīng)該在根上，并且任意子樹也應(yīng)該是一個(gè)最大堆调违。也即窟哺，除了根以外的所有節(jié)點(diǎn)i都要滿足：
A[Parent(i)] >= A[i]
2）d-堆是二叉堆的簡(jiǎn)單推廣（4-堆勝過二叉堆）
4.2.2 可合并堆——鏈?zhǔn)浇Y(jié)構(gòu)
1）二叉堆為什么合并困難？
- 數(shù)組實(shí)現(xiàn)技肩，合并需要把一個(gè)數(shù)組拷貝到另一個(gè)數(shù)組且轨，花費(fèi)為Θ(n)
- 所有支持高效合并的數(shù)據(jù)結(jié)構(gòu)都需要使用鏈?zhǔn)浇Y(jié)構(gòu)（鏈表、二叉樹等）虚婿，支持高效合并的可合并堆：
斜堆
左式堆
二項(xiàng)隊(duì)列
斐波那契堆
van Emde Boas樹
2）斜堆與左式堆
斜堆：是具有堆序的二叉樹旋奢，但是不存在對(duì)樹的結(jié)構(gòu)限制。不同于左式堆然痊，關(guān)于任意結(jié)點(diǎn)的零路徑長(zhǎng)的任何信息都不保留至朗。斜堆的右路徑在任何時(shí)候都可以任意長(zhǎng)。
因此所有操作的最壞情形為O(N)剧浸，但是攤還時(shí)間為O(lgn)-
左式堆：是具有堆序的二叉樹锹引，對(duì)于堆中的每一個(gè)結(jié)點(diǎn)，左兒子的零路徑長(zhǎng)至少與右兒子的零路徑長(zhǎng)一樣大唆香。
零路徑長(zhǎng)：定義為任一結(jié)點(diǎn)到一個(gè)沒有兩個(gè)兒子的結(jié)點(diǎn)的最短路徑長(zhǎng)嫌变。（具有0個(gè)或1個(gè)兒子結(jié)點(diǎn)的零路徑長(zhǎng)尾0，NULL為-1）
左式堆趨向于加深左路徑躬它，所以右路徑短腾啥。執(zhí)行合并的時(shí)間與右路徑的長(zhǎng)的和成正比。右路徑最長(zhǎng)不超過O(lgn)冯吓，因此合并的（最壞）時(shí)間界為O(lgn)倘待。
斜堆——左式堆
等價(jià)于
伸展樹——AVL樹
3）二項(xiàng)隊(duì)列與斐波那契堆——針對(duì)斜堆、左式堆的進(jìn)一步改進(jìn)
-
斜堆桑谍、左式堆以O(shè)(lgn)時(shí)間支持合并延柠、插入和DeleteMax
二項(xiàng)隊(duì)列進(jìn)行了改進(jìn)：以最壞O(lgn)時(shí)間支持合并、DeleteMax锣披，并且插入平均花費(fèi)常數(shù)時(shí)間贞间。
二線隊(duì)列是堆序樹（二項(xiàng)樹）的集合，稱為森林雹仿。每一個(gè)高度上至多存在一棵二項(xiàng)樹增热。高度為0的二項(xiàng)樹是一棵單節(jié)點(diǎn)樹；高度為k的二項(xiàng)樹Bk通過將一棵二項(xiàng)樹Bk-1附接到另一棵二項(xiàng)樹Bk-1的根上而構(gòu)成胧辽。
-
斐波那契堆：是二項(xiàng)隊(duì)列的推廣
通過添加兩個(gè)新的觀念：
a. DECREASE-KEY的一種不同的實(shí)現(xiàn)方法：之前的方法是把元素朝向根節(jié)點(diǎn)上濾峻仇。這種方法不能實(shí)現(xiàn)O(1)的攤還時(shí)間界，因此需要一種新的方法邑商。（斐波那契堆是直接剪切掉摄咆，放到根鏈表中）
b. 懶惰合并：只有當(dāng)兩個(gè)堆需要合并時(shí)才進(jìn)行合并凡蚜。類似于懶惰刪除。對(duì)于懶惰合并吭从，合并是低廉的朝蜘。但是因?yàn)閼卸韬喜⒉⒉粚?shí)際把樹結(jié)合在一起，所以DeleteMax操作可能會(huì)遇到很多樹涩金，從而使得這種操作的代價(jià)高昂谱醇。 特別地，一次昂貴DeleteMax必須在其前面要有大量非常低廉的合并操作
-
斐波那契堆與二叉堆時(shí)間對(duì)比
4.2.3 van Emde Boas樹——特定條件下突破比較類型堆的限制
基于比較的各種堆有時(shí)間界
二叉堆步做、紅黑樹副渴、斐波那契堆，不論是最壞或攤還情況全度，至少有一項(xiàng)重要操作需O(lgn)時(shí)間煮剧。
原因是這些數(shù)據(jù)結(jié)構(gòu)都是基于關(guān)鍵字比較來做決定的∷显兀基于比較的排序算法的下界是Ω(nlgn)說明至少有一個(gè)操作必須Ω(lgn)轿秧。因?yàn)槿绻鸌NSERT和EXTRACT-MIN操作均需要O(lgn)，那么可以通過先執(zhí)行n次INSERT操作咨堤，接著再執(zhí)行n次EXTRACT-MIN操作來實(shí)現(xiàn)O(nlgn)時(shí)間內(nèi)對(duì)n個(gè)關(guān)鍵字的排序菇篡。突破基于比較排序堆的是界——線性時(shí)間排序的啟發(fā)
當(dāng)關(guān)鍵字是有界范圍內(nèi)的整數(shù)是，可以突破排序下界限制一喘。
同理驱还，van Emde Boas樹支持優(yōu)先隊(duì)列操作以及一些其他操作（SEARCH、INSERT凸克、DELETE议蟆、MINIMUM、MAXIMUM萎战、SUCESSOR咐容、PREDECESSOR），每個(gè)操作最壞情況運(yùn)行時(shí)間為O(lglgn)蚂维。
前提是：這種數(shù)據(jù)結(jié)構(gòu)限制關(guān)鍵字為0~n-1的整數(shù)且無重復(fù)戳粒。-
van Emde Boas樹的關(guān)鍵思想
1）直接尋址
維護(hù)一個(gè)u位的數(shù)組A[0..u-1]，以存儲(chǔ)一個(gè)值來自全域{0, 1, 2, ..., u-1}的動(dòng)態(tài)集合虫啥。若值x屬于動(dòng)態(tài)集合蔚约，則A[x]位1；否則為0.
2）疊加二叉樹結(jié)構(gòu)
在位向量上疊加一棵二叉樹涂籽，來縮短位向量的掃描苹祟。內(nèi)部節(jié)點(diǎn)存儲(chǔ)的位是其兩個(gè)孩子的邏輯或。
3）疊加的二叉樹結(jié)構(gòu)是遞歸結(jié)構(gòu)，每次遞歸都以平方根大小縮減全域
4）并且一棵vEB樹中含有兩個(gè)屬性：
min存儲(chǔ)vEB樹中的最小元素（該元素不出現(xiàn)在任何子遞歸樹中）树枫；
max存儲(chǔ)vEB樹中的最大元素直焙。
如下實(shí)例，表示集合{2,3,4,5,7,14,15}：
image.png
4.2.4 配對(duì)堆——結(jié)構(gòu)限制特別少的堆（簡(jiǎn)單性造就了高效率：合并Θ(1)砂轻，DecreaseKey為O(lgn)）
配對(duì)堆的基本操作是兩個(gè)多路堆序樹的合并箕般，因此叫配對(duì)堆。
配對(duì)堆被標(biāo)示成堆序樹：
結(jié)點(diǎn)的構(gòu)造：
- LeftChild —— 左兒子
- NextSibling —— 右兄弟
- Prev —— 作為最左兒子舔清，該指針指向其父親；否則該指針指向其做兄弟
4.3 堆（優(yōu)先隊(duì)列）的應(yīng)用
4.3.1 帶寬管理（網(wǎng)絡(luò)路由器）
4.3.2 離散事件模擬
4.3.3 Dijkstra算法
4.3.4 Huffman編碼
4.3.5 Best-first搜索算法（比如A*搜索算法）
4.3.6 Prim算法
4.3.7 ROAM triangulation algorithm
ROAM——Real-time Optimally Adapting Meshes
