6. 1 模型

????????優(yōu)先隊列是允許至少下列兩種操作的數(shù)據(jù)結(jié)構(gòu)： insert(插入），它的作用是顯而易見的躺同；以及deleteMin(刪除最小者）， 它的工作是找出、返回并刪除優(yōu)先隊列中最小的元素扯俱。insert操作等價于enqueue(入隊），而deleteMin則是隊列運算dequeue(出隊）在優(yōu)先隊列中的等價操作喇澡。

????????如同大多數(shù)數(shù)據(jù)結(jié)構(gòu)那樣迅栅，有時可能要添加一些其他的操作，但這些添加的操作屬于擴展的操作晴玖，而不是圖6-1所描述的基本模型的一部分读存。

6.2 一些簡單的實現(xiàn)

????????有幾種明顯的方法可用于實現(xiàn)優(yōu)先隊列。我們可以使用一個簡單鏈表在表頭以0(1)執(zhí)行插入操作呕屎，并遍歷該鏈表以刪除最小元让簿，這又需要O(N)時間。另一種方法是始終讓鏈表保持排序狀態(tài)秀睛；這使得插入代價高昂(O(N)) 而deleteMin花費低廉(0(1))尔当。基于deleteMin的操作從不多于插入操作的事實，前者恐怕是更好的想法蹂安。

????????另一種實現(xiàn)優(yōu)先隊列的方法是使用二叉查找樹椭迎，它對這兩種操作的平均運行時間都是O(log N)锐帜。盡管插入是隨機的，而刪除則不是畜号，但這個結(jié)論還是成立的缴阎。記住我們刪除的唯一元素是最小元。 反復(fù)除去左子樹中的節(jié)點似乎會損害樹的平衡简软，使得右子樹加重蛮拔。 然而，右子樹是隨機的痹升。 在最壞的情形下语泽，即deleteMin將左子樹刪空的情形下，右子樹擁有的元素最多也就是它應(yīng)具有的兩倍视卢。 這只是在期望的深度上加了 個小常數(shù)踱卵。 注意，通過使用 棵平衡樹据过，可以把這個界變成最壞情形的界惋砂；這將防止出現(xiàn)壞的插入序列。

????????使用查找樹可能有些過分绳锅，因為它支持許許多多并不需要的操作西饵。 我們將要使用的基本的數(shù)據(jù)結(jié)構(gòu)不需要鏈，它以最壞情形時間0(logN)支持上述兩種操作鳞芙。 插入操作實際上將花費常數(shù)平均時間眷柔，若尤刪除操作的干擾，該結(jié)構(gòu)的實現(xiàn)將以線性時間建立 個具有N項的優(yōu)先隊列原朝。

6.3二叉堆

????????我們將要使用的這種工具叫作二叉堆(binary heap) , 它的使用對于優(yōu)先隊列的實現(xiàn)相當(dāng)普遍驯嘱，以至于當(dāng)堆(heap)這個詞不加修飾地用在優(yōu)先隊列的上下文中時，一般都是指數(shù)據(jù)結(jié)構(gòu)的這種實現(xiàn)喳坠。在本節(jié)鞠评，我們把二叉堆只叫作堆。像二叉查找樹一樣壕鹉，堆也有兩個性質(zhì)剃幌，即結(jié)構(gòu)性和堆序性。恰似AVL樹晾浴，對堆的一次操作可能破壞這兩個性質(zhì)中的一個负乡，因此，堆的操作必須到堆的所有性質(zhì)都被滿足時才能終止脊凰。事實上這并不難做到抖棘。

6.3. 1 結(jié)構(gòu)性質(zhì)

? ??????堆是一棵被完全填滿的二叉樹，有可能的例外是在底層，底層上的元素從左到右填入钉答。這樣的樹稱為完全二叉樹(complete binarytree)。圖6-2給出了一個例子杈抢。

????????完全二叉樹的高是 log N数尿，顯然它是0(logN)。

????????一個重要的觀察發(fā)現(xiàn)惶楼，因為完全二叉樹這么有規(guī)律右蹦，所以它可以用一個數(shù)組表示而不需要使用鏈。

????????對于數(shù)組中任一位置i上的元素歼捐，其左兒子在位置2i上何陆，右兒子在左兒子后的單元(2i +1)中，它的父親則在位置[i/2]上豹储。因此贷盲，這里不僅不需要鏈，而且遍歷該樹所需要的操作極簡單剥扣，在大部分計算機上運行很可能非彻剩快。這種實現(xiàn)方法的唯一問題在于钠怯，最大的堆大小需要事先估計佳魔，但一般這并不成問題（而且如果需要， 我們可以重新調(diào)整大谢薮丁）鞠鲜。在圖6-3中，堆大小的限界是13個元素断国。該數(shù)組有一個位置0, 后面將詳細(xì)敘述贤姆。

????????因此， 一個堆結(jié)構(gòu)將由一個(Comparable對象的）數(shù)組和一個代表當(dāng)前堆的大小的整數(shù)組成稳衬。圖6-4顯示一個優(yōu)先隊列的架構(gòu)庐氮。

????????本章我們將始終把堆畫成樹，這意味著具體的實現(xiàn)將使用簡單的數(shù)組宋彼。

6.3.2 堆序性質(zhì)

????????讓操作快速執(zhí)行的性質(zhì)是堆序性質(zhì)(heap-order property)弄砍。由于我們想要快速找出最小元，因此最小元應(yīng)該在根上输涕。如果我們考慮任意子樹也應(yīng)該是一個堆音婶，那么任意節(jié)點就應(yīng)該小于他的所有后裔。

????????應(yīng)用這個邏輯莱坎，我們得到堆序性質(zhì)衣式。在一個堆中，對于每一個節(jié)點X,X 的父親中的關(guān)鍵字小于（或等于）X 中的關(guān)鍵字，根節(jié)點除外（它沒有父親）碴卧。

https://gitee.com/sunyunjie/DataStrycturesAndAlgorithmAnalysis

6.3.3 基本的堆操作

insert（插入）

????????為將一個元素X插入到堆中弱卡，我們在下一個可用位置創(chuàng)建一個空穴，否則該堆將不是完全樹住册。如果X可以放在該空穴中而并不破壞堆的序婶博，那么插入完成。 否則荧飞，我們把空穴的父節(jié)點上的元 素移入該空穴中凡人，這樣，空穴就朝著根的方向上冒一步叹阔。 繼續(xù)該過程直到X能被放入空穴中為止挠轴。如圖6-6所示，為了插入14, 我們在堆的下一個可用位置建立一個空穴耳幢。 由于將14插入空穴破壞了堆序性質(zhì)岸晦，因此將31移入該空穴。在圖6-7中繼續(xù)這種策略睛藻，直到找出置入14的正確位置委煤。

????????如果欲插入的元素是新的最小元從而一直上濾到根處，那么這種插入的時間將長達(dá)O(logN)修档。 平均看來碧绞，上濾終止得要早；

? ??????deleteMin(刪除最小元）

? ??????deleteMin以類似于插入的方式處理吱窝。找出最小元是容易的讥邻，困難之處是刪除它。當(dāng)刪除一個最小元時院峡，要在根節(jié)點建立一個空穴兴使。由于現(xiàn)在堆少了一個元素，因此堆中最后一個元素X 必須移動到該堆的某個地方照激。如果X可以被放到空穴中发魄，那么dele七eMin完成。不過這一般不太可能俩垃，因此我們將空穴的兩個兒子中較小者移入空穴励幼，這樣就把空穴向下推了一層。重復(fù)該步驟直到X可以被放入空穴中口柳。因此苹粟，我們的做法是將X置入沿著從根開始包含最小兒子的一條路徑上的一個正確的位置。

????????圖6-9中左圖顯示了deleteMin之前的堆跃闹。刪除13后嵌削，我們必須試圖正確地將31放到堆中毛好。31 不能放在空穴中，因為這將破壞堆序性質(zhì)苛秕。于是肌访，我們把較小的兒子14置入空穴，同時空穴下滑一層（見圖6-10)艇劫。重復(fù)該過程吼驶，山于31大于19, 因此把19置入空穴，在更下一層上建立一個新的空穴港准。然后，由于31還是太大咧欣， 因此再把26置入空穴浅缸，在底層又建立一個新的空穴。最后魄咕， 我們得以將31置入空穴中（圖6-11)衩椒。這種一般的策略叫作下濾(percolate down)。在其實現(xiàn)例程中我們使用類似于在insert例程中用過的技巧來避免進(jìn)行交換操作哮兰。

????????這種操作最壞情形運行時間為 O(log N)毛萌。平均而言，被放到根處的元素幾乎下濾到堆的底層（即它所來自的那層）喝滞，因此平均運行時間為 O(log N) 阁将。

6. 5 d-堆

? ??????二叉堆是如此簡單，以至于它們幾乎總是用在需要優(yōu)先隊列的時候右遭。d-堆是二叉堆的簡單推廣做盅，它就像一個二叉堆，只是所有的節(jié)點都有d個兒子（因此窘哈，二叉堆是2-堆）吹榴。

????????圖 6-19 表示的是一個 3-堆。注意滚婉，d-堆要比二叉堆淺得多图筹，它將 insert操作的運行時間 改進(jìn)為 O(logd N)。然而让腹，對于大的 d, deleteMin 操作費時得多远剩，因為雖然樹是淺了，但是 d個兒子中的最小者是必須要找出的骇窍，如使用標(biāo)準(zhǔn)的算法民宿，這會花費d-1次比較，于是將操作的用時提高到 O(d logd N)像鸡。如果 d 是常數(shù)活鹰，那么當(dāng)然兩個的運行時間都是 O(log N)哈恰。雖然仍然可以使用一個數(shù)組，但是志群，現(xiàn)在找出兒子和父親的乘法和除法都有個因子 d, 除非 d 是 2 的幕着绷，否則將會大大增加運行時間，因為我們不能再通過移一個二進(jìn)制位來實現(xiàn)除法了锌云。d-堆在理論上很有趣荠医，因為存在許多算法，其插入次數(shù)比 dele匡Min 的次數(shù)多得多（因此理論上的加速是可能的）桑涎。當(dāng)優(yōu)先隊列太大而不能完全裝入主存的時候彬向，d-堆也是很有用的。在這種情況下攻冷，d-堆 能夠以與B樹大致相同的方式發(fā)揮作用娃胆。最后，有證據(jù)顯示等曼，在實踐中4-堆可以勝過二叉堆里烦。

6.6 左式堆

? ??????設(shè)計一種堆結(jié)構(gòu)像二叉堆那樣有效地支持合并操作（即以o(N)時間處理一個merge)而且 只使用一個數(shù)組似乎很困難。 原因在于禁谦，合并似乎需要把一個數(shù)組拷貝到另一個數(shù)組中去胁黑，對于相同大小的堆這將花費時間O(N)。 正因為如此州泊，所有支持有效合并的高級數(shù)據(jù)結(jié)構(gòu)都需要使用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)丧蘸。

6. 6. 1 左式堆性質(zhì)

????????我們把任一節(jié)點X的零路徑長(null pathleng th) npl (X)定義為從X到一個不具有兩個兒子的節(jié)點的最短路徑的長。因此遥皂，具有0個或一個兒子的節(jié)點的npl 為o, 而npl(null)= -1触趴。在圖6-20的樹中， 零路徑長標(biāo)記在樹的節(jié)點內(nèi)渴肉。

????????注意冗懦，任一節(jié)點的零路徑長比它的各個兒子節(jié)點的零路徑長的最小值大l。這個結(jié)論也適用少于兩個兒子的節(jié)點仇祭，因為null的零路徑長是-1披蕉。

????????左式堆性質(zhì)是：對于堆中的每一個節(jié)點X, 左兒子的零路徑長至少與右兒子的零路徑長相等。圖6-20中只有一棵樹乌奇，即左邊的那棵樹滿足該性質(zhì)没讲。這個性質(zhì)實際上超出了它確保樹不平衡的要求，因為它顯然偏重于使樹向左增加深度礁苗。確實有可能存在由左節(jié)點形成的長路徑構(gòu)成的樹（而且實際上更便于合并操作） 因此爬凑，我們就有了名稱左式堆(leftist heap)。

????????因為左式堆趨向于加深左路徑试伙，所以右路徑應(yīng)該短嘁信。事實上于样，沿左式堆右側(cè)的右路徑確實是該堆中最短的路徑。否則潘靖，就會存在過某個節(jié)點X的一條路徑通過它的左兒子穿剖，此時X 就破壞了左式堆的性質(zhì)。

定理6.2 在右路徑上有r個節(jié)點的左式樹必然至少有2^r-1個節(jié)點卦溢。

6.6.2 左式堆操作

????????對左式堆的基本操作是合并糊余。 注意，插入只是合并的特殊情形单寂，因為我們可以把插入看成 是單節(jié)點堆與一個大的堆的merge贬芥。 首先，我們給出一個簡單的遞歸解法宣决，然后介紹如何能夠非遞歸地執(zhí)行該解法蘸劈。 我們的輸入是兩個左式堆H1和H2, 見圖6-21。 讀者應(yīng)該驗證疲扎，這些堆確實是左式堆昵时。 注意捷雕， (最小的元素在根處椒丧。 除數(shù)據(jù)、左引用和右引用所用空間外救巷，每個節(jié)點還要有一個指示零路徑長的項壶熏。

????????如果這兩個堆中有 個堆是空的，那么我們可以返回另外一個堆浦译。 否則棒假，合并這兩個堆， 比較它們的根精盅。 首先帽哑，我們遞歸地將具有大的根值的堆與具有小的根值的堆的右子堆合并,, 在本例中，我們遞歸地將H2與h1的根在8處的右子堆合并叹俏， (18得到圖6-22中的堆妻枕。

? ??????由于這棵樹是遞歸形成的，而我們尚未 對算法描述完畢粘驰，因此屡谐，現(xiàn)在還不能說明該是如何得到的。 不過蝌数，有理由假設(shè)愕掏，最后 的結(jié)果是一個左式堆，因為它是通過遞歸的步驟得到的顶伞。 這很像歸納法證明中的歸納 圖6-22 將H2 與凡的右子堆合并的結(jié)果假設(shè)饵撑。 既然我們能夠處理基準(zhǔn)情形（發(fā)生在一棵樹是空的時候）剑梳，當(dāng)然可以假設(shè)，只要能夠完成合并那么遞歸步驟就是成立的,這是遞歸

6.7 斜堆

????????斜堆(skew heap)是左式堆的自調(diào)節(jié)形式肄梨，實現(xiàn)起來極其簡單阻荒。 斜堆和左式堆間的關(guān)系類似于伸展樹和AVL樹間的關(guān)系。 斜堆是具有堆序的二叉樹众羡，但不存在對樹的結(jié)構(gòu)限制侨赡。 不同于左 式堆，關(guān)于任意節(jié)點的零路徑長的任何信息都不再保留粱侣。 斜堆的右路徑在任何時刻都可以任意長羊壹，因此，所有操作的最壞情形運行時間均為O(N)齐婴。 然而油猫，正如伸展樹一樣，可以證明（見第11章）對任意M次連續(xù)操作柠偶，總的最壞情形運行時間是O(Mlog N)情妖。 因此，斜堆每次操作的攤還開銷 (amortized cost) 為 O(logN)诱担。

? ??????與左式堆相同毡证，斜堆的基本操作也是合并操作。merge例程還是遞歸的蔫仙，我們執(zhí)行與以前完全相同的操作料睛，但有一個例外，即：對于左式堆摇邦，我們查看是否左兒子和右兒子滿足左式堆結(jié)構(gòu)性質(zhì)恤煞， 并在不滿足該性質(zhì)時將它們交換。但對于斜堆施籍，交換是無條件的居扒，除那些右路徑上所有節(jié)點的最大者不交換它的左右兒子的例外外， 我們都要進(jìn)行這種父換丑慎。這個例外就是在自然遞歸實現(xiàn)時所發(fā)生的情況喜喂，因此它實際上根本不是特殊情形。此外立哑，證明時間界也是不必要的夜惭，但是，由于這樣的節(jié)點肯定沒有右兒子铛绰，因此執(zhí)行交換是不明智的（在我們的例子中诈茧，該節(jié)點沒有兒子，因此我們不必為此擔(dān)心）捂掰。另外敢会，仍設(shè)我們的輸入是與前面相同的兩個堆曾沈，見圖6-31如果我們遞歸地將H2與H1

的根在8處的子堆合并，那么將得到圖6-32中的堆鸥昏。

?????????注意塞俱，因為右路徑可能很長，所以遞歸實現(xiàn)可能由于缺乏椑艨澹空間而失敗障涯，盡管在其他方面性能是可接受的。 斜堆有一個優(yōu)點膳汪，即不需要附加的空間保留路徑長以及不需要測試以確定何時交換兒子唯蝶。 精確確定左式堆和斜堆的右路徑長的期望值是一 個尚未解決的問題（后者無疑更為困難）。 這樣的比較將更容易確定平衡信息的輕微遺失是否可由缺乏測試來補償遗嗽。

6.8 二項隊列

????????雖然左式堆和斜堆都在每次操作以O(shè)(logN)時間有效地支持合并粘我、插入和deleteMin,但還是有改進(jìn)的余地，因為我們知道痹换，二叉堆以每次操作花費常數(shù)平均時間支持插入征字。二項隊列支持所有這三種操作，每次操作的最壞情形運行時間為0(logN) , 而插入操作平均花費常數(shù)時間娇豫。

6. 8. 1 二項隊列結(jié)構(gòu)

????????二項隊列(binomial queue)與我們已經(jīng)看到的所有優(yōu)先隊列的實現(xiàn)的區(qū)別在于匙姜，一個二項隊 列不是一棵堆序的樹，而是堆序的樹的集合锤躁，稱為森林(forest)搁料。每一棵堆序樹都是 有約束的形式或详，叫作二項樹(binomial tree , 后面將看到該名稱的由來是顯然的）系羞。每一個高度上至多存在一棵二項樹。高度為0的二項樹是一棵單節(jié)點樹霸琴；高度為k的二項樹凡通過將一棵二項樹 Bk -I附接到 另 一棵二項樹 Bk-I的根上而構(gòu)成椒振。圖6-34顯示二項樹 B0,B1,B2,B3以及B4.

????????從圖中看到，二項樹隊由一個帶有兒子B0, B1梧乘，澎迎。。选调。夹供，BK-1的根組成。高度為k的二項樹恰好有2k個節(jié)點仁堪，而在深度d 處的節(jié)點數(shù)是二項系數(shù)(d)哮洽。如果我們把堆序施加到二項樹上并允許任意高度上最多一棵二項樹，那么就能夠用二項樹的集合表示任意大小的優(yōu)先隊列弦聂。例如鸟辅，大小為13 的優(yōu)先隊列可以用森林B3, B2, B氛什。表示。我們可以把這種表示寫成1101, 它不僅以二進(jìn)制表示了13'而且也表示這樣的事實：在上述表示中匪凉，B3, B2, B枪眉。出現(xiàn)，而B1則沒有再层。