第六章：優先隊列(堆)

[TOC]

思考如下場景,老師布置了很多作業,現在你需要將作業列印出來,你將作業文件依照隊列的形式放入待列印列表中,但此時,你希望最重要(或者是馬上就要上交)的作業優先列印出來.此時,隊列結構顯然不能滿足我們的需求,這時候我們考慮一種名為優先隊列(priority queue)的數據結構,或者稱之為堆.

6.1 模型

優先隊列至少允許以下兩種操作:

Insert(插入)：等價於隊列中 Enqueue(入隊).

DeleteMin(刪除最小者)：找出、返回和刪除優先隊列中的最小元素.等價於隊列中 Dequeue(出隊).

6.2 一些簡單的實現

使用一個簡單鏈表再表頭以 $ O(1) $ 執行插入操作,並遍歷該鏈表以刪除最小元,這需要 $ O(N) $ 的時間.

另一種方法,始終讓表表示排序轉檯,這會使得插入操作花費 $ O(N) $ 時間,而 DeleteMin 操作花費 $ O(1) $ 時間.*考慮到 DeleteMin 操作並不多於 Insert 操作,因此在這二者之間,第一種方法可能更好.

再一種方法,使用二叉查找樹,這樣保證了這兩種操作的時間複雜度都是 $ O(log N) $ . 儘管插入是隨機的,而操作不是,這個結論依舊成立.反覆刪除左子樹的節點會損害樹的平衡,但是考慮到右子樹是隨機的,在最壞的情況下,即 DeleteMin 將左子樹刪空的情況下,右子樹擁有的元素最多也就是它應有的二倍,這只是在期望的深度上增加了一個常數.

6.3 二叉堆

二叉堆(binary heap)：如同二叉查找樹一樣,二叉堆有兩個性質,結構性和堆序性,如同AVL樹一樣,對二叉堆的一次操作可能破壞其中一個性質.同時,需要提醒的是,二叉堆可以簡稱為堆(heap),因為用二叉堆實現優先隊列十分普遍.

6.3.1 結構性質

完全二叉樹(complete binary tree)：完全填滿的二叉樹,有可能的例外是在底層,底層上的元素從左到右依次填入.如下圖.

一棵高度為 $ h $ 的完全二叉樹有 $ 2^h $ 到 $ 2^ - 1 $ 個節點,這意味著,對於擁有 $ N $ 個節點的完全二叉樹而言,它的高度為 $ lfloor logN
floor $ ,顯然為 $ O(logN) $.十分重要的一點,由於完全二叉樹具有規律性,所以它可以用數組來表示.可以代替指針.如下.

對於數組中任意一個位置 $ i $ 上的元素,其左兒子在位置 $ 2i $ 上,右兒子在位置 $ 2i + 1 $ 上,它們的父親在位 置$ lfloor frac
floor $ 上.用數組表示的優點不再贅述,但有一個缺點需要提醒,使用數組表示二叉堆需要實現估計堆的大小,但這對於典型情況不成問題.

6.3.2 堆序性質

堆序(heap order)：使操作被快速執行的性質,依據堆的性質,最小元總是可以在根處找到.

在一個堆中,任意子樹也是一個堆.在一個堆中,對於每一個節點 $ X $, $ X $ 的父親中關鍵字小於或者等於 $ X $ 中的關鍵字,根節點除外,因為它沒有父親.

6.3.3 基本的堆操作

Insert 插入 考慮將一個元素 $ X $ 插入堆中,我們將在下一個位置建立一個空穴,否則該堆將不再是完全二叉樹.

如果 $ X $ 可以放到該空穴中而不影響堆的序,那麼插入操作完成.

否則,我們將這個空穴的父親節點上的元素移動到該空穴上,這樣,空穴便隨著根的方向一直向上進行,直到滿足步驟 1 為止.這種策略叫上濾(percolate up).如下圖所示,嘗試插入關鍵字 14 .

如果插入的元素是新的最小值,那麼它將被推到頂端.在頂端, $ i = 1 $ ,我們可以跳出循環,可以在 $ i = 0 $ 處放置一個很小的值使得循環中止.這個值我們稱之為標記(sentinel),類似於鏈表中頭節點的使用,通過添加一條啞信息(dummy piece of infomation),避免每次循環都要執行一次測試,從而節省了一點時間.如果插入的元素是新的最小元,已知過濾到根部,那麼這種插入的時間複雜度顯然是 $ O(logN) $ .

DeleteMin 刪除最小元 DeleteMin 的操作類似於 Insert 操作.找到最小元是很容易的,而刪除它是比較困難的.當刪除一個最小元時,在根節點處產生一個空穴,由於現在堆少了一個元素,因此堆中最後一個元素 $ X $ 必須移動到該堆的某個位置.

如果 $ X $ 可以移動到空穴中去,那麼 DeleteMin 操作完成.

鑒於 1. 中的步驟不太可能發生,因此我們考慮 $ X $ 不能移動到空穴中的情況,我們將空穴的兩個兒子中較小的一個(考慮到是最小堆)移入空穴中,這樣一來就把空穴向下推了一格,重複這個步驟直到 $ X $ 可以被放到空穴中.這種策略叫做下濾(percolate down).如下例:

其中需要注意的一點是,當堆中存在偶數個元素時,此時將會遇到一個節點只有一個兒子的情況,我們不必須保證節點不總有兩個兒子,因此這就涉及到一個附加節點的測試.

這種演算法的最壞運行時間為 $ O(logN) $ ,平均而言,被放到根除的元素幾乎下濾到堆的底層.

6.3.4 其他堆的操作

對於最小堆(min heap)而言,求最小元易如反掌,但是求最大元,卻不得不採取遍歷的手段.對於最大堆找最小元亦是如此.

事實上,一個堆所蘊含的關於序的信息很少,因此,如果不對堆進行線性搜索,是沒有辦法找到任何特定的關鍵字的.為了說明這一點,在下圖所示的大型堆結構(具體元素沒有給出).

我們看到,關於最大值的元素所知道的唯一信息是:該元素位於樹葉上.但是,有近半數的元素位於樹葉上,因此該信息是沒有什麼用處的.出於這個原因,如果我們要知道某個元素處在什麼位置上,除了堆之外,還要用到諸如散列表等某些其他的數據結構.

如果我們假設通過某種其他方法得知每一個元素的位置,那麼有幾種其他的操作的開銷將變小.下列三種這樣的操作均以對數最壞情形時間運行.

DecreaseKey 降低關鍵字的值DecreaseKey(P, $ Delta $ , H)操作將降低在位置 P 處關鍵字的值,降低的幅度為 $ Delta $( $ Delta > 0 $ ),由於這可能會破壞堆的序,因此必須通過上濾對堆進行調整.該操作堆系統管理程序是游泳的,系統管理程序能夠使它們的程序以最高的優先順序來運行.

IncreaseKey 增加關鍵字的值IncreaseKey(P, $ Delta $ , H)操作將增加在位置 P 處關鍵字的值,增值的幅度為 $ Delta $( $ Delta > 0 $ ).可以通過下濾來完成.許多調度程序自動地降低正在過多小號CPU時間的進程的優先順序.

Delete 刪除Delete(P, H)操作刪除堆中位置 P 上的節點.這通過首先執行DecreaseKey(P, $ infty $ , H),然後再執行 DeleteMin(H).當一個進程被用戶中止(非正常中止)時,它不許從優先隊列中除去.

BuildHeap 構建堆BuildHeap(H)操作把 N 個關鍵字作為輸入並把它們放到空堆中.顯然,這可以使用 N 個 Insert 操作來完成.由於每個 Insert 操作將會花費平均 $ O(1) $ 時間和最壞 $ O(logN) $ 時間,因此該操作的總的運行時間是 $ O(N) $ 平均時間而不是 $ O(NlogN) $ 最壞情形時間.由於這是一種特殊的執行,沒有其他操作的干擾,也讓且我們已經直到了該指令能夠以線性平均時間運行,因此,期望能夠保證線性時間界的考慮是合乎情理的.下面我們看平均時間是怎麼得到的.一般的演算法是將 N 個關鍵字以任意順序放入樹中,保持結構特性.此時,如果 percolateDown(i) 從節點 i 下濾,那麼執行下列代碼創建一棵具有堆序的樹(heap-ordered tree)

如下例

為了確定 BuildHeap 的運行時間的界,我們確定虛線條數的界,這可以通過計算樹中所有節點的高度和來得到,它是虛線的最大條數,現在我們說明,該和為$ O(N) $

定理：包含 $ 2^ - 1 $ 個節點高為 $ b $ 的理想二叉樹(perfect binary tree)的節點的高度的和為 $ 2^ - 1 - ( b + 1 ) $ 證明：容易看出以下規律:

則所有節點的高度和 $ S = 2^ * b + 2^ *( b - 1 ) + ... + 2^ * 1+ 2^ * 0 = $

利用裂項相消,得到$ S = 2^ - 1 - ( b + 1 ) $

6.4 優先隊列的應用

6.4.1 選擇問題

選擇問題(selection problem)：從一組 N 個數而要確定其中第 k 個最大者.

演算法一: 把這些元素依次讀入數組並給他們排序,同時返回適當的元素.該演算法的時間複雜度為 $ O(N^2) $

演算法二：先把前 k 個元素讀入數組並按照遞減的順序排序,之後,將剩下的元素逐個讀入,當新元素讀入時,如果它小於數組中的第 k 個元素則忽略,否則就將它放到數組中正確的位置上.同時將數組中的一個元素擠出數組,當演算法中止的時候,第 k 個位置上的元素作為關鍵字返回即可.該演算法的時間複雜度是 $ O(kN) $,當 $ k = lceil frac
ceil $ 時,該演算法時間複雜度為 $ O(N^2) $ .注意,對於任意的 k ,我們可以求解對稱的問題:找出第 (N - k + 1) 個最小的元素,從而 $ k = lceil frac
ceil $ 實際上時這兩種演算法最困難的情況,此時 k 處的值被稱為中位數(median).

演算法三：為簡單起見,假設我們只考慮找出第 k 個最小的元素.我們將 N 個元素讀入一個數組,然後堆數組應用 BuildHeap 演算法,最後,執行 k 次 DeleteMin 操作.從該堆中最後提取的元素就是我們需要的答案.顯然,改變堆序的性質,我們可以求原式問題:找出第 k 個最大的元素. 演算法的正確性顯然. 考慮演算法的時間複雜度,如果使用 BuildHeap ,構造堆的最壞情形用時為 $ O(N) $ ,而每次 DeleteMin 用時 $ O(logN) $ .由於有 k 次 DeleteMin,因此我們得到總的運行時間為 $ O(N + klogN) $ .

如果 $ k = O(frac ) $ ,那麼運行時間取決於 BuildHeap 操作,即O(N).

對於大的 k 值,運行時間為 $ O(klogN) $.

如果 $ k = lceil frac
ceil $,那麼運行時間為 $ Theta(NlogN) $

演算法四：回到原始問題:找出第 k 個最大的元素.在任意時刻我們都將維持 k 個最大元素的集合 S 。在前 k 個元素讀入之後,當再讀入一個新的元素時,該元素將與第 k 個最大元素進行比較,記這第 k 個最大的元素為 $ Sk $ .注意, $ Sk $ 是集合 S 中最小的一個元素.如果新元素比 $ Sk $ 大,那麼用新元素替代集合 S 中的 $ Sk $ .此時,集合 S 中將有一個新的最小元素,它與偶可能是剛剛添加進的元素,也有可能不是.當輸入終止時,我們找到集合 S 中的最小元素,並將其返回,這邊是答案. 演算法四思想與演算法二相同.不過,在演算法四中,我們用一個堆來實現集合 S ,前 k 個元素通過調用依次 BuildHeap 以總時間 $ O(k) $ 被置入堆中.處理每個其餘的元素花費的時間為 $ O(1) + O(logk) $,其中 $ O(1) $ 部分是檢查元素是否進入 S 中, O(logk)部分是再必要時刪除 $ S_k $ 並插入新元素.因此總時間是 $ O(k + ( N - k )logk) = O( Nlogk) $.如果 $ k = lceil frac
ceil $,那麼運行時間為 $ Theta(NlogN) $.

6.4.2 時間模擬

我們假設有一個系統,比如銀行,顧客們到達並站隊等在哪裡直到 k 個出納員中有一個騰出手來.我們關注在於一個顧客平均要等多久或隊伍可能有多長這樣的統計問題.

對於某些概率分布以及 k 的取值,答案都可以精確地計算出來.然而伴隨著 k 逐漸變大,分析明顯地變得困難.

模擬由處理中的時間組成.這裡有兩個事件.

一個顧客的到達.

一個顧客的離開,從而騰出一名出納員.

我們可以使用概率函數來生成一個輸入流,它由每個顧客的到達時間和服務時間的序偶組成,並通過到達時間排序.我們不必使用一天中的精準時間,而是通過名為滴答(tick)的單位時間量. 進行這種模擬的一種方法是在啟動處在 0 滴答處到額一台摸擬鐘錶.讓鐘錶一次走一個滴答,同時查詢是否有一個事件發生.如果有,那麼我們處理事件,搜集統計資料.當沒有顧客留在輸入流中且所有出納員都閑置,模擬結束. 但是這種模擬問題,它運行的時間不依賴顧客數量或者時間數量,而是依賴於滴答數,但是滴答數又不是實際輸入.不妨假設將時鐘的單位改成滴答的千分之一併將輸入中的所有時間乘以 1000 ,那麼結果便是,模擬用時增加了1000倍. 避免這種問題的關鍵在於在每一個階段讓重表直接走到下一個事件時間,從概念上來看這是容易做到的.在任一時刻,可能出現的下一個時間或者是下一個顧客到達,或者是有一個顧客離開,同時一個出納員閑置.由於可以得知將發生事件的所有時間,因此我們只需要找出最近的要發生的事件並處理這個事件.

如果這個事件是有顧客離開,那麼處理過程包括搜集離開的顧客的統計資料及檢驗隊列看看是否還有其他顧客在等待.如果有,那麼我們加上這位顧客,處理所需要的統計資料,計算該顧客將要離開的時間，並將離開事件假到等待發生的事件集中區.

如果事件是有顧客到達，那麼我們檢查閑置的出納員.如果沒有，那麼我們把該到達時間放置到隊列中去；否則，我們分配顧客一個出納員，計算顧客離開的時間，並將離開事件加到等待發生的事件集中區. 在等待的顧客隊伍可以實現為一個隊列.由於我們需要找到最近的將要發生的事件，合適的辦法是將等待發生的離開的結合編入到一個優先隊列中.下一個事件是下一個到達或者下一個離開.

考慮以上演算法的時間複雜度，如果有 C 個顧客（因此有 2C 個事件 ）和 k 個出納員，那麼模擬的運行時間將會是 $ O( Clog(k+1)) $ ,因為計算和處理每個事件花費時間為 $ O(logH) $ ,其中 $ H = k + 1 $ 為堆的大小.

6.5 d-堆

d-堆是二叉堆的推廣，它像一個二叉堆，但是所有的節點都有 d 個兒子（注意，二叉堆是一個2-堆）.

如上圖所示，3-堆。

6.6 左式堆

Merge 合併操作，堆而言，合併操作是最困難的操作。

考慮到堆結構無法用數組實現以 $ O(N) $ 高效的合併操作。因此，所有支持高效合併的高級數據結構都需要使用指針。

左式堆(leftist heap)：它與二叉樹之間的唯一區別是，左式堆不是理想平衡的，而實際上是趨向於非常不平衡。它具有相同的堆序性質，如有序性和結構特性。

6.6.1 左式堆的性質

零路徑長(null path length, NPL)：從任一節點 $ X $ 到一個沒有兩個兒子的節點的最短路徑長。因此，具有 0 個或 1 個兒子的節點的 Npl 為 0，而 Npl(NULL) = -1. 注意，任一節點的零路徑長比它諸兒子節點的零路徑長的最小值多 1 。這個結論也適用少於兩個兒子的節點，因為 NULL 的零路徑長為 -1 .

性質：對於左式堆中的每一個節點 $ X $ ,左則日子的零路徑長至少與右兒子的零路徑長一樣大。如下圖所示：

在圖示中，右邊的樹並不是左式堆，因為他不滿足左式堆的性質。左式堆的性質顯然更加使樹向左增加深度。確實有可能存在由左節點形成的長路徑構成的樹（實際上這更加便於合併操作），故此，我們便有了左式堆這個名稱。

定理：在右路徑上有 $ r $ 個節點的左式樹必然至少有 $ 2^r - 1 $ 個節點。證明：數學歸納法。若$ r = 1 $ ，則必然至少存在一個樹節點；假設定理對 $ r = k $ 成立，考慮在右路徑上有 $ k + 1 $ 個節點的左式樹，此時，根具有在右路徑上含 $ k $ 個節點的右子樹，以及在右路徑上至少包含 $ k $ 個節點的左式樹（否則它便不是左式樹）。對這兩個子樹應用歸納假設，得知每棵子樹上最少含有 $ 2^k - 1 $ 個節點，再加上根節點，於是這顆樹上至少有有 $ 2^ - 1 $ 個節點。原命題得證。

推廣：從上述定理我們立即可以得到，$ N $ 個節點的左式樹有一條右路徑最多包含 $ lfloor log(N+1)
floor $ 個節點。

6.6.1 左式堆的操作

合併 首先，注意，插入只是合併的一個特殊情形。首先，我們給出一個簡單的遞歸解法，然後介紹如何能夠非遞歸地施行該解法。如下圖，我們輸入兩個左式堆 $ H1 $，$ H2 $.

除去使用數據、左指針、右指針外還需要一個只是零路徑長的項。

如果這兩個堆中有一個是空的，那麼我們可以直接返回另一個非空的堆。

否則，想要合併兩個堆，我們需要比較它們的根。回想一下，最小堆中根節點小於它的兩個兒子，並且子樹都是堆。我們將具有大的根值得堆與具有小的根值得堆的右子樹合併。在本例中，我們遞歸地將 $ H2 $ 與 $ H1 $ 中根在 8 處的右子堆合併，得到下圖：

注意，因為這顆樹是通過遞歸形成的，我們有理由說，合成的樹依然是一棵左式樹。現在，我們讓這個新堆成為 $ H_1 $ 中根的右兒子。如下圖：

最終得到的堆依然滿足堆序的性質，但是，它並不是左式堆。因為根的左子樹的零路徑長為 1 ，而根的右子樹的零路徑長為 2 .左式樹的性質在根處遭到了破壞。不過，很容易看到，樹的其餘部分必然是左式樹。這樣一來，我們只要對根部進行調整即可。方法如下：只要交換根的做兒子和右兒子，如下圖，並更新零路徑長，就完成了 Merge . 新的零路徑長是新的右兒子的零路徑長加 1 .注意，如果零路徑長不更新，那麼所有的零路徑長將都是 0 ，而堆也不再是左式堆，只是隨機的。

6.7 斜堆

斜堆(skew heap)：斜堆是具有堆序的二叉樹，但是不存在對樹的結構限制。它是左式堆的自調節形式，但不同於左式堆，關於任意節點的零路徑長的任何信息不做保留。斜堆的右路徑在任何時候都可以任意長，因此，所有操作的最壞情形運行時間為 $ O(N) $ . 與左式堆相同，斜堆的基本操作也是 Merge 合併。但是有一處例外，對於左式堆，我們查看是否左兒子和右兒子滿足左式堆堆序性質並交換那些不滿足性質者；對於斜堆，除了這些右路徑上所有節點的最大者不交換它們的左右兒子之外，交換是無條件的。

6.8 二項隊列

6.8.1 二項隊列結構

二項隊列(binomial queue)：一個二項隊列不是一棵堆序的樹，而是堆序樹的集合，稱為森林(forest).

堆序樹中的每一棵都是有約束的形式，叫做二項樹（binomial tree）.

每一個高度上之多存在一棵二項樹。高度為 0 的二項樹是一顆單節點樹；高度為 k 的二項樹 $ Bk $ 是通過將一棵二項樹 $ B$ 附接到另一棵二項樹 $ B$ 的根上而構成的。如下圖：二項樹 $ B0、B1、B2、B3、B4 $ .

從圖中看到，二項樹 $ Bk $ 由一個帶有兒子 $ B0 , B1, B2,..., B$ 的根組成。高度為 k 的二項樹恰好有 $ 2^k $ 個節點，而在深度 d 處的節點數為 $ Ck^d $ .

如果我們把堆序施加到二項樹上並允許任意高度上最多有一棵二項樹，那麼我們能夠用二項樹的集合惟一地表示任意大小地優先隊列。for example：大小為 13 的優先隊列可以用森林 $ B0 , B2, B3 $ 表示。我們可以把這種表示寫成 1101 ，這不僅以二進位表示了 13 也表述 $ B1 $ 樹不存在的事實。

6.8.2 二項隊列的操作

FindMin：可以通過搜索所有樹的樹根找出。由於最多有 $ logN $ 棵不同的樹，因此找到最小元的時間複雜度為 $ O(logN) $ . 另外，如果我們記住當最小元在其他操作期間變化時更新它，那麼我們也可保留最小元的信息並以 $ O(1) $ 時間執行該操作。

Merge：合併操作基本上是通過將兩個隊列加到一起來完成的。考慮兩個二項隊列 $ H1,H2 $ ,他們分別具有六個和七個元素，見下圖。

令 $ H_3 $ 是新的二項隊列。

由於 $ H1 $ 沒有高度為 0 的二項樹而 $ H2 $ 擁有，因此我們就用 $ H2 $ 中高度為 0 的二項樹作為 $ H3 $ 的一部分。

由於 $ H1、H2 $ 都擁有高度為 1 的二項樹，因此我們令二者合稱為 $ H_3 $ 中高度為 2 的二項樹。

現存有三棵高度為 2 的樹，我們選擇其中兩個和合成高度為 3 的樹，另外一棵放到 $ H_3 $ 中。

由於現在 $ H1、H2 $ 不存在高度為 3 的樹，合併結束。$ H_3 $ 如下圖：

考慮 Merge 操作的時間複雜度，由於幾乎使用任意合理的實現方法合併兩棵二項樹均花費常數時間，而總存在 $ O(logN) $ 棵二項樹，因此合併在最壞情形下花費時間為 $ O(logN) $ .為了使操作更高效，我們需要將這些樹放到按照高度排血的二項隊列中。

Insert：插入操作實際上是特殊情形的合併，我們只需要創建一棵單節點樹並執行一次合併操作。這種操作的最壞運行時間也是 $ O(logN) $ .更加準確地說，如果元素將要插入的那個優先隊列不存在的最小的 $ B_k $ ,那麼運行時間與 i+1 成正比.

DeleteMin：通過首先找出一棵具有最小根的二項樹來完成。令該樹為 $ Bk $ ,並令原始的優先隊列為 $ H $ ,我們從 H 的樹的森林中除去二項樹 $ Bk $ ,形成新的二項樹隊列 $ H" $ ,再除去 $ Bk $ 的根，得到一些二項樹 $ B0 , B1, B2,..., B$ ,它們共同形成優先隊列 $ H"" $ .合成 $ H" $ 與 $ H"" $ ,操作結束。例如，假設有二項隊列 $ H3 $ ,如下圖：其中最小的根是 12，因此我們得到兩個優先隊列 $ H" $ 和 $ H"" $ ,如下圖：最後，合併 $ H" $ 和 $ H"" $ ,完成 DeleteMin 操作。

分析時間複雜度，注意，DeleteMin 操作將原隊列一分為二，找出含有最小元素的樹並創建隊列 $ H" $ 和 $ H"" $ 花費時間為 $ O(logN) $ 時間，合併 $ H" $ 和 $ H"" $ 又花費時間為 $ O(logN) $ 時間。因此，整個 DeleteMin 操作的時間複雜度為 $ O(logN) $ .

6.8.3 二項隊列的實現

二項樹的每一個節點包含一個數據，第一個兒子以及右兄弟。二項樹中的諸兒子以遞增的次序排列。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！