數據結構優先級隊列第6章6.1問題引入6.2優先級隊列的定義6.3二叉堆6.4多叉堆6.5可并堆6.6優先級隊列應用6.7拓展延伸6.8應用場景6.1問題引入：帶優先級的服務處理問題：第3章介紹的隊列能夠按先到先得的方式來處理，但實際問題中（例如醫院或者銀行）還有可能需要考慮加急的情況，更一般地說就是優先級。如何按優先級進行處理？關鍵：出隊的順序需要由元素本身的優先級來決定，而不是進隊的順序。6.2優先級隊列的定義優先級隊列是一種特殊的隊列。與普通隊列相比，相同點：都支持進隊和出隊操作。不同點：優先級隊列的出隊順序按事先規定的優先級順序進行。ADTPriorityQueue{數據對象：

元素取自全集U的可重集合E，表示優先級隊列中包含的元素。數據關系：

全集U中的元素須滿足嚴格弱序。基本操作：

（省略初始化、銷毀、清除內容、判斷為空、查詢元素個數等操作）

Insert(pq,x)：在優先級隊列pq

中插入元素x。

ExtractMin(pq)：從優先級隊列pq

中刪除優先級最高（也就是值最小）的元素，并返回。

PeekMin(pq)：返回優先級隊列pq

中優先級最高的元素（元素仍然保留在優先級隊列中）。}優先級隊列的實現優先級隊列可以用線性表來實現。然而，使用線性表實現時出隊操作需要將當前優先級隊列中的所有元素都檢查一遍，從而找到優先級最高的元素。假設優先級隊列中元素個數為n，這種實現下出隊操作的復雜度是O(n)，效率較低。一般會使用二叉堆等更加高效的數據結構來實現優先級隊列。6.3二叉堆二叉堆是一種常見的堆，常用來實現優先級隊列。二叉堆最早由J.W.J.Williams于1964年提出，作為支持堆排序的一種數據結構。6.3.1二叉堆的定義二叉堆是父結點元素和子結點元素滿足一定大小關系的完全二叉樹。根據條件不同，可分為最小堆和最大堆。最小堆：如果完全二叉樹T中的所有父子結點對都有父結點的元素不大于子結點的元素，則稱T為最小堆。最大堆：如果完全二叉樹T中的所有父子結點對都有父結點的元素不小于子結點的元素，則稱T為最大堆。（最小堆和最大堆的區別只在于父子結點元素之間的大小關系）為簡便起見，本章中的二叉堆（也包括其他種類的堆）都以最小堆為例進行講解，最大堆的情況可類推得到。6.3.1二叉堆的定義

結點結點下標1234566.3.2二叉堆的操作二叉堆的基本操作是堆元素的上調和下調。（這里的“上”和“下”是指用一般習慣畫出二叉堆的樹表示后元素在調整過程中的走向）在上調和下調操作的基礎上，可實現堆元素的插入、刪除，以及建堆操作。設數組h.data[]中保存著二叉堆中的元素。在對二叉堆進行操作的過程中，可能會出現不滿足二叉堆性質的時刻，為表述方便，仍用堆來稱呼此時的狀態。二叉堆的上調操作上調操作：如果堆中某結點i小于其父結點p，此時可以交換結點i和結點p的元素，也就是把結點i沿著堆的這棵樹往“上”調整。此時，再看新的父結點與它的大小關系。重復該過程，直到結點i被調到根結點位置或者和新的父結點大小關系滿足條件。如圖演示了一次二叉堆的上調操作的過程，元素1從開始的葉結點位置一直調整到了根結點。二叉堆的上調操作在實現時，可以通過以下方法避免交換，從而減少賦值操作的次數。SiftUp先將結點i的元素保存在臨時變量中，隨著調整將父結點的元素往“下”移動，最后再將原來結點i的元素填入合適的位置。由此得到上調操作的算法如下：對于上調操作而言，循環的次數不會超過樹的高度，因此時間復雜度為O(logn)。算法6-1：二叉堆的上調操作SiftUp(h,i)輸入：堆h

和上調起始位置i輸出：上調后滿足堆性質的helem←h.data[i]while

i>1且elem<h[i/2]do//當前結點小于其父結點|h.data[i]←h.data[i/2]//將i的父結點元素下移|i←i/2//i指向原結點的父結點，即向上調整endh.data[i]←elem二叉堆的下調操作下調操作：如果堆中某結點i大于其子結點，則要將其向“下”調整。調整時需要注意，對于有兩個子結點的情況，如果兩個子結點均小于結點i，交換時應選取它們中的較小者，只有這樣才能保證調整之后三者的關系能夠滿足堆的性質。重復該過程，直到結點i被調到葉結點位置或者和新的子結點大小關系滿足條件。如圖演示了一次二叉堆的下調操作的過程，元素7從開始的根結點位置一直調整到了葉結點，注意每次要和左右子結點中值較小的元素進行交換。二叉堆的下調操作下調操作同樣可以使用上調操作的方法來避免交換操作，使用該方法實現的下調操作算法如下。對于下調操作而言，循環的次數也不會超過樹的高度，因此時間復雜度為O(logn)。算法6-2：二叉堆的下調操作SiftDown(h,i)輸入：堆h

和下調起始位置i輸出：下調后滿足堆性質的hlast←h.size//這是最后一個元素的位置elem←h.data[i]whiletrue

do|child←2i//child當前是i的左孩子的位置|if

child<last

且h.data[child+1]<h.data[child]then//如果i有右孩子并且右孩子更小||child←child+1//child更新為i的右孩子的位置|elseifchild>last//如果i是葉子結點||break//已經調整到底，跳出循環|end|if

h.data[child]<elemthen//若較小的孩子比elem小||h.data[i]←h.data[child]//將較小的孩子結點上移||i←child//i指向原結點的孩子結點，即向下調整|else//若所有孩子都不比elem小||break//則找到了elem的最終位置，跳出循環|endendh.data[i]←elem二叉堆的插入操作插入操作：有了上調與下調兩個基本操作后，堆的插入操作就可以實現為向堆中追加待插入的元素，然后用上調操作將其調整到合適的位置來完成堆的調整，時間復雜度同樣是O(logn)。插入操作算法如下所示。算法6-3：二叉堆的插入操作Insert(h,x)輸入：堆h

和待插入元素x輸出：將元素插入后的堆h.size←h.size+1last←h.sizeh.data[last]←x//暫時將x放入最后一個元素的位置SiftUp(h,last)//從最后一個位置上調二叉堆的刪除操作刪除操作：刪除操作所要提取的最小元素就是堆中的第一個元素，然后可以把堆中的最后一個元素挪到第一個位置，并通過下調操作將這個元素調整到合適的位置，時間復雜度是O(logn)。刪除操作算法如下所示。算法6-4：二叉堆的刪頂操作ExtractMin(h)輸入：堆h輸出：h中的最小元，以及刪除了最小元素后的堆hmin_key←h.data[1]//這是將要返回的最小元last←h.size//這是刪除前最后一個元素的位置h.size←h.size-1h.data[1]←h.data[last]//暫時將刪除前最后一個元素放入根的位置SiftDown(h,1)//從根結點下調returnmin_key二叉堆的樸素建堆操作樸素建堆操作：對于任意一組元素，可以通過逐個上調的方式把它們轉化為一個堆，相當于依次插入堆中，算法如下所示。使用上述方法進行建堆，堆中后一半的元素進行上調時都可能需要O(logn)的時間，因此總的時間復雜度是O(nlogn)。算法6-5：二叉堆的樸素建堆操作MakeHeapUp(h)輸入：存儲在h

中的數據輸出：滿足堆性質的堆hlast←h.size//這是最后一個元素的位置fori←2to

last

do|SiftUp(h,i)end二叉堆的快速建堆操作

算法6-6：二叉堆的快速建堆操作MakeHeapDown(h)輸入：存儲在h

中的數據輸出：滿足堆性質的堆hlast←h.size//這是最后一個元素的位置fori←last/2downto1do//last/2是最后一個元素的父結點的位置|SiftDown(h,i)end6.4多叉堆

多叉堆的上調操作可以根據以上性質擴展二叉堆的SiftUp操作，使得它支持多叉堆。算法6-7：多叉堆的上調操作SiftUpD(h,d,i)輸入：堆h、堆的分叉數d

和上調起始位置i輸出：上調后滿足d叉堆性質的helem←h.data[i]while

i>0and

elem<h.data[(i?1)/d]do|h.data[i]←h.data[(i?1)/d]|i←(i?1)/dendh.data[i]←elem多叉堆的下調操作同理，也可以擴展二叉堆的SiftDown操作，要注意向下比較時要看所有的子結點。算法6-8：多叉堆的下調操作SiftDownD(h,d,i)輸入：堆h、堆的分叉數d

和下調起始位置i輸出：將堆h

中的元素下調以滿足堆性質last←h.size-1

//這是最后一個元素的位置elem←h.data[i]whiletrue

do|child←i

|for

k←1tod

do//找所有孩子中最小的||if

d×i+k≤last

且h.data[d×i+k]<h.data[child]then|||child←d×i+k//child更新為更小的孩子的位置||end|end|ifchild=i

then//前面for循環未執行，i是葉結點||break//已經調整到底，跳出循環|end|if

h.data[child]<elem

then//若最小的孩子比elem小||h.data[i]←h.data[child]//將最小的孩子結點上移||i←child//i指向原結點的孩子結點，即向下調整|else//若所有孩子都不比elem小||break//則找到了elem的最終位置，跳出循環|endendh.data[i]←elem多叉堆的分析

6.5可并堆*一些算法需要高效地支持堆的合并操作，也就是把兩個堆的元素合并到一個堆中，同時保持堆的性質。如果采用二叉堆結構，合并操作的實現方式是將其中一個堆（一般是元素較少的那個）中的全部元素逐一插入到另一個堆中，或者直接將兩個堆的元素連接在一起再執行一次建堆操作，復雜度都比較高。能夠高效支持合并操作的堆被稱為可并堆。常見的可并堆有左堆、斜堆、二項堆等。與二叉堆相比，可并堆的形狀往往是不規則的，因此在實現時需要用指針來表示結點之間的連接關系。值得一提的是，多數可并堆會將合并操作作為最基本的操作，插入操作可由原有堆與待插入元素本身構成的單元素堆的合并操作來完成，刪除操作則是將原有堆刪除結點后所產生的所有分離的子樹進行合并。6.5.1左堆左堆，也稱為左式堆，是可并堆的一種。左堆是二叉堆的一個變種，不要求是完全二叉樹，且每個結點有一個額外的權值，用于在操作過程中保持堆的形態。左堆有多種定義，本書中的左堆以常見的高偏左堆為例進行講解。在高偏左堆中，使用空路徑長度NPL作為這個額外的權值，定義為以結點x為根的子樹中最近的空缺葉結點離結點x的距離。如圖所示，每個結點旁邊的值代表該結點的NPL值，

灰色矩形結點為空缺葉結點。除了滿足堆性質外，左堆中每個結點還需要滿足

右子結點的NPL值不大于左子結點的NPL值。根據這個性質，左堆中每個結點的左子樹的高度

往往大于右子樹，因此被稱為左堆。左堆的性質設一個左堆的結點個數為n，根結點為r，根結點的NPL值為npl(r)，則有以下性質成立：(a)n≥2npl(r)?1。(b)npl(r)≤log(n+1)。(c)r的右子結點路徑（不斷沿右子結點移動直到右子樹為空所組成的路徑）長度為npl(r)。上述性質的證明如下：(a)由NPL值的定義可知，該左堆的前npl(r)?1層都是滿的（否則npl(r)的值會變小），累加這些層的結點數可得。(b)可由(a)推出。(c)由NPL值的定義，以及左堆中一個結點右子結點的NPL值不大于它的左子結點的NPL值可知，對左堆中任意一個結點x及它的右子結點y，有npl(x)=npl(y)+1，進而得到(c)。左堆的合并操作左堆的合并：合并操作以兩個左堆h1和h2為輸入，返回一個新的左堆h，h中包含了h1和h2中的所有元素。合并操作的基本思想是將h1和h2中的根結點進行比較，將較小的根結點作為h的根結點，然后遞歸地將較小根的右子樹與較大根樹進行合并，合并結果作為h的根的右子樹。在合并結束后，我們需要檢查h的左右子樹的NPL值，如果右子樹的NPL值大于左子樹的NPL值，那么我們將左右子樹進行交換。這樣，我們就可以保證h的右子樹的NPL值不大于左子樹的NPL值，從而滿足左堆的性質。左堆的合并操作合并操作過程如下所示。算法6-9：左堆的合并操作LeftistMerge(h1,h2)輸入：待合并的兩個左堆h1和h2輸出：合并后的左堆if

h1=NILthen|

returnh2endifh2=NILthen|

returnh1endifh1.key>h2.key

then|

returnLeftistMerge(h2,h1)//保證第一個堆的根結點是較小的那個end//現在h1.key≤h2.keyif

h1.left=NILthen//如果左子樹為空，則h1肯定是單結點樹|h1.left

←h2else|h1.right←LeftistMerge(h1.right,h2)|ifh1.left.npl<h1.right.npl

then//保證左堆性質||Swap(h1.left,h1.right)|end|h1.npl

←h1.right.npl+1//右子樹的npl值一定比較小endreturnh1左堆的合并操作下面舉例說明左堆的合并過程：如下圖所示，將兩個左堆合并，其中一個有5個結點，另一個有1個結點。為此，需要遞歸合并結點9和以結點7為根的子樹。在合并結束后，維護有關結點的NPL值，發現結點3處左堆性質不滿足，需要交換左右子結點。交換后，合并過程結束。左堆的合并操作考慮該合并操作的時間復雜度。可以發現，該過程每遞歸一層，h1或h2中的一個將會跳到其右子結點，因此最多遞歸O(log?n+log?m)層后會到達一個空結點，其中n和m分別為h1和h2中的元素個數。在每一層遞歸中，我們需要比較h1和h2的根結點，然后遞歸地合并較小根的右子樹，因此每一層的時間復雜度為O(1)。因此，合并操作的時間復雜度為O(log?n+log?m)。當n和m同階時，合并操作的時間復雜度為O(log?n)。左堆的其他操作下面介紹左堆的其他操作，其中的修改操作幾乎都可以轉化為合并操作。插入元素：插入操作可以轉化為合并操作。可將待插入的元素構造為只含有一個元素的左堆，然后將這個左堆與原來的左堆合并即可。由于合并操作的時間復雜度為O(log?n)，因此插入操作的時間復雜度也為O(log?n)。建堆：如果元素個數較少，可以考慮逐一插入空堆；如果元素個數較多，可以按照二叉堆的建堆方式建立左堆（二叉堆一定符合左堆的性質），時間復雜度為O(n)。查詢最小值：左堆的最小值必然在根結點上，時間復雜度為O(1)。刪除最小值：如果需要刪除左堆的最小值，將根結點刪除后，再將其左右子樹合并即可，時間復雜度為O(log?n)。左堆的其他操作刪除任意元素：將待刪除結點的左右子樹合并，取代其位置后，依次向上考慮其祖先結點：如果其祖先結點的左右子樹的NPL值不滿足左堆性質，則將其左右子樹進行交換；如果NPL值需要更新，則進行相應的更新。重復以上步驟，直到NPL值不再發生變化。時間復雜度為O(log?n)。修改任意元素：可采取先刪除后插入的方式，時間復雜度為O(log?n)。假如試圖通過直接修改后上調/下調的方式進行操作，由于左堆的高度、深度并沒有保證，可能會達到最壞線性的時間復雜度。6.5.2斜堆斜堆是一種類似于左堆的可并堆，其插入、刪除、合并的時間復雜度雖然在最壞情況下可能達到線性，但是其均攤時間復雜度（在6.5.4節中介紹）仍然為單次操作O(log?n)。斜堆與左堆都是由二叉樹實現的堆，但斜堆不再需要維護每個結點的額外權值，而是通過時常交換左右子樹的方式來確保時間復雜度不會退化。我們仍然先介紹斜堆的合并操作，再基于合并操作介紹插入、刪除等操作。斜堆的合并操作斜堆的合并操作：與左堆類似，我們可以通過遞歸地合并兩個斜堆來實現合并操作。對于兩個斜堆，首先比較它們的根結點，將權值較小的根結點作為新的根結點，然后遞歸地合并其右子結點與根權值較大的斜堆。與左堆不同的是，在遞歸合并完成之后，將其左右子結點進行交換（左堆可以認為是在左偏性質不滿足時交換，而斜堆則是每次都交換）。斜堆的合并操作斜堆合并過程如下所示。算法6-10：斜堆的合并操作SkewMerge(h1,h2)輸入：待合并的兩個斜堆

h1和h2輸出：合并后的斜堆ifh1=NILthen|returnh2endifh2=NILthen|returnh1endifh1.key>h2.key

then|returnSkewMerge(h2,h1)end//現在h1.key

≤h2.keyh1.right

←SkewMerge(h1.right,h2)Swap(h1.left,h1.right)returnh1斜堆的合并操作同樣地，我們用一個例子描述斜堆的合并操作：如圖所示，將兩個斜堆合并，根據斜堆的定義，每個結點不需要維護額外的權值。合并過程中不斷向右子樹移動，插入完成后將移動路徑上的節點的左右子樹交換。斜堆的合并操作合并操作在最壞情況下可達O(n)的線性時間復雜度，例如其中一個斜堆是一條向右的單鏈。但是，其均攤時間復雜度仍然為每次合并O(log?n)。“均攤”在這里指的是：雖然單次合并操作最壞情況下為O(n)的線性時間復雜度，但如果從空數據結構開始總共進行任意n次合并操作，其總時間復雜度可保證為O(nlogn)，也就是總時間不會退化為O(n2)的復雜度。斜堆合并的O(logn)復雜度的均攤分析具體證明過程較為復雜，有興趣的讀者可以參考相關資料。斜堆的其他操作下面介紹斜堆的其他操作，其中的修改操作幾乎都可以轉化為合并操作。插入操作：與左堆類似，斜堆的插入操作可以轉化為與僅含單個元素的斜堆的合并操作，時間復雜度為均攤O(log?n)。建堆操作：可以轉化為與二叉堆的建堆操作一致的方式，時間復雜度為O(n)。查詢最小值操作：斜堆的最小值必然在根結點上，時間復雜度為O(1)。刪除最小值操作：與左堆類似，如果需要刪除斜堆的最小值，可將根結點刪除后，再將其左右子樹合并即可。時間復雜度為均攤O(log?n)。刪除任意元素操作：將待刪除結點的左右子結點合并，取代其位置即可，時間復雜度為均攤O(log?n)。修改關鍵字操作：同左堆，建議采用先刪除后插入的方式，時間復雜度為均攤O(log?n)。6.5.3二項堆

度01236.5.3二項堆二項堆是由多棵二項樹組成的，且滿足：每棵二項樹均滿足堆性質，例如，對于最小堆，則任何結點的權值都不大于其所有子結點的權值；所有二項樹的度數互不相同。考慮總共含有n個元素的二項堆，由于每棵二項樹的元素個數必然為2的冪，那么將n進行二進制分解，即可得到所對應的二項樹的度數。例如n=13，其二進制表示為1101，那么對應的二項樹的度數為0、2、3。因此，二項堆的結構是可以根據元素個數n唯一確定的。與其他可并堆的思路類似，我們先介紹二項堆的合并操作，再基于合并操作介紹插入、刪除等操作。二項堆的合并操作既然二項堆是由多棵二項樹組成的，那么我們首先考慮二項樹的合并。合并兩棵度數均為k的二項樹是非常簡單的，只需要比較兩棵二項樹的根結點，將權值較小的根結點作為新的根結點，而將權值較大的根結點作為新的根結點的第一個子結點，即可形成一棵度數為k+1且滿足堆性質的二項樹。由于僅需要做一次比較與連接操作，合并兩棵二項樹的時間復雜度僅為O(1)。如下圖為一個例子：35682647←比較→26473568二項堆的合并操作二項堆的合并操作：由于二項堆是由多棵二項樹組成的，那么可以將二項堆的合并操作轉化為多次二項樹的合并操作。對于兩個二項堆，我們取出其中所有的二項樹，如果存在兩棵二項樹的度數相同，那么我們將它們合并為一棵度數更大的二項樹，并重復這樣的合并操作，直到不存在度數相同的二項樹，即可得到合并后的二項堆。實際代碼實現當中，可以從小到大考慮所有的度數。由于每次合并兩棵二項樹的時間復雜度為O(1)，而最多需要合并O(logn)次，因此二項堆的合并操作的時間復雜度為O(logn)。二項堆的其他操作插入操作：可以方便地轉化為合并操作。我們將待插入的元素構造為只含有一個元素的二項堆，然后將這棵二項堆與原來的二項堆合并即可。由于合并操作的時間復雜度為O(logn)，因此插入操作的時間復雜度也O(logn)。建堆操作：可以轉化為插入操作，我們將所有的元素依次插入到空的二項堆中即可。盡管單次插入操作的時間復雜度為O(logn)，但向空堆插入n個元素的總時間復雜度經分析為O(n)。查詢最小值操作：由于二項堆是由多棵二項樹組成的，那么我們只需要遍歷所有的二項樹，找到其中最小的根結點即可。由于至多有O(logn)棵二項樹，因此查詢最小值操作的時間復雜度為O(logn)。另外，也可以考慮維護一個指向最小根結點的指針，每次進行其他修改操作后均更新該指針，這樣查詢最小值操作的時間復雜度就可以降為O(1)。二項堆的其他操作刪除最小值操作：首先查詢到最小值的位置，其必為某棵二項樹的根結點。該二項樹去除根結點后，會“分裂”為多棵二項樹。我們將這些二項樹視為一個臨時二項堆，然后將這個臨時二項堆與原來的二項堆合并即可。由于合并操作的時間復雜度為O(logn)，因此刪除最小值操作的時間復雜度也為O(logn)。減小關鍵字操作：與二叉堆類似，先修改待操作結點的權值，然后將其與父結點進行比較，如果滿足堆性質，則結束操作；否則，將其與父結點交換內容，并重復向上比較，直到滿足堆性質或者到達根結點。由于二項樹的高度為O(logn)，因此減小關鍵字操作的時間復雜度為O(logn)。刪除操作：先將其權值減小為負無窮，再執行刪除最小值操作，時間復雜度為O(logn)。修改關鍵字操作：先刪除該元素，再插入新元素，時間復雜度為O(logn)。與二叉堆不同，由于二項堆的每個結點可能擁有多個子結點，因此直接通過父子間比較交換的方式修改關鍵字可能會造成復雜度的退化。6.5.4均攤分析在進行數據結構和算法的時間復雜度分析時，有些場景下最壞情況的時間復雜度可能過于悲觀，不能準確反映實際的運行時間。尤其是對于一些動態數據結構，在對其進行連續的某個特定操作時，每個操作的運行時間變化范圍可以很大。為了讓復雜度分析更加具有實際意義，往往會更加看重一系列操作的平均時間復雜度。一般會使用均攤分析來計算這種場景下的時間復雜度。常見的均攤分析方法有三種，分別是：聚合法、記賬法、勢能法。聚合法聚合法的核心思想：先求出n個操作的總時間上限為T(n)，然后得出均攤復雜度為T(n)/n。以二項堆為例，盡管二項堆的各項操作通常都具有O(logn)的時間復雜度，但在一些場景下可以用均攤分析得出更準確的復雜度。考慮如下的場景：向空的二項堆通過逐個插入的方式共插入n個元素，按上述結論總時間復雜度為O(nlogn)，但通過更加細致的分析可以得到一個更緊的界為O(n)。用均攤分析的語言講，每次插入的均攤時間復雜度為O(1)。下面我們來解釋這個結論。聚合法向二項堆插入元素分為增加結點和合并兩個步驟。由于每次增加結點的時間復雜度都是O(1)，我們主要分析合并所花費的時間。先觀察向空二項堆插入若干次元素時，引起的二項樹合并情況和插入后的二項樹列表（注意到二項堆的形態僅與其中元素個數有關，無須考慮具體元素內容），如下表所示：可以觀察到這樣的結論：所有奇數次插入不會引起任何二項樹合并，偶數次插入會引起兩棵規模為20的二項樹的合并，每4次插入會引起兩棵規模為21的二項樹的合并，以此類推。第幾次插入引起的二項樹合并插入后的二項樹列表1無20=1220+20→2121=23無20+21=3420+20→21，21+21→2222=45無20+22=5620+20→2121+22=5………………聚合法

記賬法

記賬法采用記賬法來分析二項堆元素插入的過程，可以取第i次插入操作的均攤代價bi=1。由于該操作的實際代價ci為該次插入操作引起的合并次數，那么兩者之差di=1?(第i次操作的合并次數)。對于任意的n，前n次操作的記賬總和Sn=n?(n次操作的總合并次數)。由聚合法中的分析可知，n次操作的總合并次數不超過n次，這就表明了Sn?0，該均攤代價的估計是有效的，均攤復雜度為O(1)。勢能法

勢能法

勢能法對于涉及均攤復雜度的數據結構，使用中需要確認能否接受它的最壞情況。以一個在線購物業務為例，如果每100個用戶的前99個需要1秒的時間處理，第100個需要100秒的時間，我們可以認為處理每個用戶的“均攤時間”為1.99秒，但實際上對于這個“倒霉的”第100個用戶來說是不可接受的。因此，在應用均攤復雜度的數據結構編寫軟件時，尤其需要注意系統中是否有實時性要求。6.6優先級隊列應用：哈夫曼樹的構建第5.5節講了哈夫曼樹。在構建哈夫曼樹的過程中，算法CreateHuffmanTree會持續地從一個二叉樹集合中取出帶權路徑長度最小和次小的兩棵二叉樹，并把合并后的樹加回到集合里。這個過程是優先級隊列的典型應用，可以將二叉樹的帶權路徑長度定為優先級（帶權路徑長度越小優先級越高），分別使用ExtractMin和Insert來完成從集合取出最小、次小以及加回到集合的操作。為了提高算法的效率，通常使用二叉堆作為優先級隊列的實現。由于二叉堆的插入和刪除元素操作都是O(logn)的時間復雜度，建堆的時間復雜度是O(n)，整個算法在建堆之后一共要進行2n-2次刪除和n-1次插入操作，因此總的復雜度為O(nlogn)。用二叉堆實現的優先級隊列能夠高效地支持諸如構建哈夫曼樹這樣的算法。6.7拓展延伸優先級隊列和堆有很多可以拓展的方面，下面介紹雙端優先級隊列和對頂堆。6.7.1雙端優先級隊列有的應用需要同時支持獲取集合中的最大和最小元素的操作，我們把這樣的數據結構稱為雙端優先級隊列。與普通的優先級隊列相比，雙端優先級隊列的ADT增加了ExtractMax和PeekMax操作。雙端優先級隊列可以使用一個最大堆和一個最小堆配合來實現。在實現時，這兩個堆中的元素要分別增加指向另外一個堆中對應元素的指針域，并在元素插入或者刪除時做好相應的維護。第12章要介紹的自平衡二叉搜索樹（如紅黑樹、AA樹、伸展樹等）也可以用來實現雙端優先級隊列。此外，雙端優先級隊列也有一些專用的方法，下面簡單介紹最小最大堆。6.7.1雙端優先級隊列最小最大堆與二叉堆的基本原理相似，本身是一棵完全二叉樹的結構。它結合了最小堆和最大堆的特性：位于偶數層（0、2、4、……）的結點小于它的所有后代結點，而位于奇數層（1、3、5、……）的結點大于它的所有后代結點，如圖所示。同理，還可以定義最大最小堆。6.7.1雙端優先級隊列插入操作Insert：向最小最大堆插入元素時，先將待插入的元素置于數組末尾，然后根據情況上調該元素在堆中的位置。調整時，與二叉堆的區別在于二叉堆每次都和上一層的元素（父結點）進行比較，而最小最大堆在和父結點比較一次之后會進行連續的跨層比較（也就是和祖父結點進行比較），直到根結點。查詢最小元素PeekMin：最小最大堆的最小元素一定是根結點。查詢最大元素PeekMax：最小最大堆的最大元素一定是根結點的