6. 1 模型

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

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

6.2 一些簡(jiǎn)單的實(shí)現(xiàn)

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

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

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

6.3二叉堆

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

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

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

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

????????一個(gè)重要的觀察發(fā)現(xiàn)，因?yàn)橥耆鏄溥@么有規(guī)律，所以它可以用一個(gè)數(shù)組表示而不需要使用鏈。

????????對(duì)于數(shù)組中任一位置i上的元素，其左兒子在位置2i上，右兒子在左兒子后的單元(2i +1)中，它的父親則在位置[i/2]上。因此，這里不僅不需要鏈，而且遍歷該樹所需要的操作極簡(jiǎn)單，在大部分計(jì)算機(jī)上運(yùn)行很可能非常快。這種實(shí)現(xiàn)方法的唯一問題在于，最大的堆大小需要事先估計(jì)，但一般這并不成問題（而且如果需要， 我們可以重新調(diào)整大?。?。在圖6-3中，堆大小的限界是13個(gè)元素。該數(shù)組有一個(gè)位置0, 后面將詳細(xì)敘述。

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

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

6.3.2 堆序性質(zhì)

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

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

https://gitee.com/sunyunjie/DataStrycturesAndAlgorithmAnalysis

6.3.3 基本的堆操作

insert（插入）

????????為將一個(gè)元素X插入到堆中，我們?cè)谙乱粋€(gè)可用位置創(chuàng)建一個(gè)空穴，否則該堆將不是完全樹。如果X可以放在該空穴中而并不破壞堆的序，那么插入完成。 否則，我們把空穴的父節(jié)點(diǎn)上的元 素移入該空穴中，這樣，空穴就朝著根的方向上冒一步。 繼續(xù)該過程直到X能被放入空穴中為止。如圖6-6所示，為了插入14, 我們?cè)诙训南乱粋€(gè)可用位置建立一個(gè)空穴。 由于將14插入空穴破壞了堆序性質(zhì)，因此將31移入該空穴。在圖6-7中繼續(xù)這種策略，直到找出置入14的正確位置。

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

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

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

????????圖6-9中左圖顯示了deleteMin之前的堆。刪除13后，我們必須試圖正確地將31放到堆中。31 不能放在空穴中，因?yàn)檫@將破壞堆序性質(zhì)。于是，我們把較小的兒子14置入空穴，同時(shí)空穴下滑一層（見圖6-10)。重復(fù)該過程，山于31大于19, 因此把19置入空穴，在更下一層上建立一個(gè)新的空穴。然后，由于31還是太大， 因此再把26置入空穴，在底層又建立一個(gè)新的空穴。最后， 我們得以將31置入空穴中（圖6-11)。這種一般的策略叫作下濾(percolate down)。在其實(shí)現(xiàn)例程中我們使用類似于在insert例程中用過的技巧來避免進(jìn)行交換操作。

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

6. 5 d-堆

? ??????二叉堆是如此簡(jiǎn)單，以至于它們幾乎總是用在需要優(yōu)先隊(duì)列的時(shí)候。d-堆是二叉堆的簡(jiǎn)單推廣，它就像一個(gè)二叉堆，只是所有的節(jié)點(diǎn)都有d個(gè)兒子（因此，二叉堆是2-堆）。

????????圖 6-19 表示的是一個(gè) 3-堆。注意，d-堆要比二叉堆淺得多，它將 insert操作的運(yùn)行時(shí)間 改進(jìn)為 O(logd N)。然而，對(duì)于大的 d, deleteMin 操作費(fèi)時(shí)得多，因?yàn)殡m然樹是淺了，但是 d個(gè)兒子中的最小者是必須要找出的，如使用標(biāo)準(zhǔn)的算法，這會(huì)花費(fèi)d-1次比較，于是將操作的用時(shí)提高到 O(d logd N)。如果 d 是常數(shù)，那么當(dāng)然兩個(gè)的運(yùn)行時(shí)間都是 O(log N)。雖然仍然可以使用一個(gè)數(shù)組，但是，現(xiàn)在找出兒子和父親的乘法和除法都有個(gè)因子 d, 除非 d 是 2 的幕，否則將會(huì)大大增加運(yùn)行時(shí)間，因?yàn)槲覀儾荒茉偻ㄟ^移一個(gè)二進(jìn)制位來實(shí)現(xiàn)除法了。d-堆在理論上很有趣，因?yàn)榇嬖谠S多算法，其插入次數(shù)比 dele匡Min 的次數(shù)多得多（因此理論上的加速是可能的）。當(dāng)優(yōu)先隊(duì)列太大而不能完全裝入主存的時(shí)候，d-堆也是很有用的。在這種情況下，d-堆 能夠以與B樹大致相同的方式發(fā)揮作用。最后，有證據(jù)顯示，在實(shí)踐中4-堆可以勝過二叉堆。

6.6 左式堆

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

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

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

????????注意，任一節(jié)點(diǎn)的零路徑長(zhǎng)比它的各個(gè)兒子節(jié)點(diǎn)的零路徑長(zhǎng)的最小值大l。這個(gè)結(jié)論也適用少于兩個(gè)兒子的節(jié)點(diǎn)，因?yàn)閚ull的零路徑長(zhǎng)是-1。

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

????????因?yàn)樽笫蕉掩呄蛴诩由钭舐窂剑杂衣窂綉?yīng)該短。事實(shí)上，沿左式堆右側(cè)的右路徑確實(shí)是該堆中最短的路徑。否則，就會(huì)存在過某個(gè)節(jié)點(diǎn)X的一條路徑通過它的左兒子，此時(shí)X 就破壞了左式堆的性質(zhì)。

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

6.6.2 左式堆操作

????????對(duì)左式堆的基本操作是合并。 注意，插入只是合并的特殊情形，因?yàn)槲覀兛梢园巡迦肟闯?是單節(jié)點(diǎn)堆與一個(gè)大的堆的merge。 首先，我們給出一個(gè)簡(jiǎn)單的遞歸解法，然后介紹如何能夠非遞歸地執(zhí)行該解法。 我們的輸入是兩個(gè)左式堆H1和H2, 見圖6-21。 讀者應(yīng)該驗(yàn)證，這些堆確實(shí)是左式堆。 注意， (最小的元素在根處。 除數(shù)據(jù)、左引用和右引用所用空間外，每個(gè)節(jié)點(diǎn)還要有一個(gè)指示零路徑長(zhǎng)的項(xiàng)。

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

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

6.7 斜堆

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

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

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

?????????注意，因?yàn)橛衣窂娇赡芎荛L(zhǎng)，所以遞歸實(shí)現(xiàn)可能由于缺乏?？臻g而失敗，盡管在其他方面性能是可接受的。 斜堆有一個(gè)優(yōu)點(diǎn)，即不需要附加的空間保留路徑長(zhǎng)以及不需要測(cè)試以確定何時(shí)交換兒子。 精確確定左式堆和斜堆的右路徑長(zhǎng)的期望值是一 個(gè)尚未解決的問題（后者無疑更為困難）。 這樣的比較將更容易確定平衡信息的輕微遺失是否可由缺乏測(cè)試來補(bǔ)償。

6.8 二項(xiàng)隊(duì)列

????????雖然左式堆和斜堆都在每次操作以O(shè)(logN)時(shí)間有效地支持合并、插入和deleteMin,但還是有改進(jìn)的余地，因?yàn)槲覀冎?，二叉堆以每次操作花費(fèi)常數(shù)平均時(shí)間支持插入。二項(xiàng)隊(duì)列支持所有這三種操作，每次操作的最壞情形運(yùn)行時(shí)間為0(logN) , 而插入操作平均花費(fèi)常數(shù)時(shí)間。

6. 8. 1 二項(xiàng)隊(duì)列結(jié)構(gòu)

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

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