第九章 堆和堆排序

高級算法設計與分析

第九章堆與堆排序堆堆排序O(nlgn)最壞運行時間—像歸并排序。Sortsinplace—像插入排序。結合了兩個算法的優(yōu)點。一個使用一種數(shù)據(jù)結構（堆）來排序的排序算法。優(yōu)先隊列主要內容二叉樹

是一個有根結點的有序樹，其中每個結點最多有兩個孩子結點，并且左孩子結點和右孩子結點可區(qū)分(也就是說他們有不同屬性)。有序樹

是一個有根結點的樹，其中每個結點的孩子結點都是有序的(第一個孩子結點，第二個孩子結點，等等)。二叉樹(1)兩個不同的二叉樹在一個二叉樹中:一個結點的深度是從這個結點到根結點的簡單路徑的邊數(shù)。一顆樹T的深度

是樹中所有結點最大的深度。一個結點的高度

=從該結點到一個葉子結點的最長簡單路徑的邊數(shù)。一棵樹T的高度

=樹的根結點的高度=樹的深度二叉樹(2)結點2的深度=1樹T

的深度=3結點2的高度=2樹T的高度=3完全二叉樹

是一個所有葉子結點在同樣深度，而且每個非葉節(jié)點都有兩個孩子結點的二叉樹。完全二叉樹高度為3的完全二叉樹在完全二叉樹中，高度為

h的結點數(shù)？2h+1–1有

n

個結點的完全二叉樹的高度?lg(n+1)–1深度為d

的

近似完全二叉樹

滿足下面兩個條件:只考慮深度為d–1時是完全二叉樹深度為d

的結點都在靠左部分近似完全二叉樹(1)高度為3的近似完全二叉樹有n

個結點的近似完全二叉樹T

的高度是多少?假設T

不是一個完全二叉樹。假設高度是h。T

包含一個深度為h–1的完全二叉樹，而且有一些深度為

h的結點，因此,2h–1<n<2h

+1–1

2h≤n<2h

+1

lgn–1<h

≤lgn

h=(lgn)

高度為h

的近似完全二叉樹有多少結點?假設有

n

個結點，

那么2h≤n<2h

+1

n=(2h)近似完全二叉樹(2)一個(二叉)堆是一個

近似完全二叉樹

:結點中存儲的數(shù)值來自一個有序的集合。每個結點存儲的數(shù)值滿足一種

堆的性質.兩種堆的性質:最大堆性質:每個結點存儲的數(shù)值≥該結點的孩子節(jié)點存儲的數(shù)值。最大值存儲在根結點最小堆性質:每個結點存儲的數(shù)值

≤該結點的孩子節(jié)點存儲的數(shù)值。最小值存儲在根結點堆兩種類型的堆:最大堆滿足最大堆性質

最小堆

滿足最小堆性質

最大堆舉例

堆(續(xù))如何實現(xiàn)一個堆?如果用數(shù)組存儲堆，結點外的數(shù)字是結點的數(shù)組下標。結點里的數(shù)字是每個結點存儲的值，也叫

keys

。一個堆可以用一個數(shù)組A來實現(xiàn)。根結點是

A[1].A[i]的左孩子結點=A[2i].A[i]的右孩子結點

=A[2i+1].A[i]的父節(jié)點

=A[

i/2].使用數(shù)組,找父節(jié)點和孩子結點的操作可以很快計算。用數(shù)組實現(xiàn)堆用數(shù)組實現(xiàn)最大堆數(shù)組實現(xiàn)(續(xù))弧線連接父親節(jié)點和孫子節(jié)點Max-Heapify:維護最大堆性質;代價O(lgn)時間Build-Max-Heap:從一個無序數(shù)組建成一個最大堆;代價

(n)時間Heapsort:排序一個數(shù)組；代價

O(nlgn)Max-Heap-Insert,Heap-Extract-Max,Heap-Increase-Key,和Heap-Maximum:這些操作可用堆實現(xiàn)優(yōu)先隊列

。

堆的基本操作Max-Heapify

維護最大堆的性質。調用Max-Heapify之前:A[i],可能比它的孩子結點小。條件:i

的左和右子樹已經(jīng)是最大堆。調用Max-Heapify之后:以i

為根的子樹是一個最大堆。維護堆的性質主要思想:比較A[i],A[Left(i)],andA[Right(i)]如果有需要,把A[i]與其較大的一個孩子結點交換在堆中繼續(xù)向下比較和交換，直到以

i

為根的子樹是一個最大堆。

算法Max-Heapify運行時間:樹的高度是lgn

將

A[i]向下移動一層需要常數(shù)時間O(lgn)演示Max-Heapify結點2違反最大堆性質。比較結點2和其孩子結點,將結點2與其較大的孩子交換。繼續(xù)向下比較交換,直到以存儲4的結點為根結點的子樹成為一個最大堆。自底向上的過程把一個無序的數(shù)組

A建成一個最大堆在建堆過程中,只需要考慮非葉節(jié)點。子數(shù)組

A[

n/2+1..n]中的元素對應的所有結點都是葉子結點。A[

n/2]是非葉節(jié)點中數(shù)組下標最大的。A[

n/2]的左孩子是

A[2

n/2]。

建堆建堆:舉例循環(huán)不變:每一次for循環(huán)的開始，結點

i+1,i+2,...,n

都是一個最大堆的根結點。初始化:結點

n/2+1,

n/2+2,...,n

都是葉子結點,他們都是一個最大堆的根結點。

循環(huán)開始時

i=

n/2,上述循環(huán)不變?yōu)檎姹３?結點i

的孩子結點的數(shù)組下標比i

大，因此，根據(jù)循環(huán)不變，它們都是最大堆的根。因此，調用Max-Heapify(A,i,n)的條件被滿足，該過程使得結點

i

成為一個最大堆的根。遞減

i

的值為下一次循環(huán)重新建立循環(huán)不變。中止:當i=0,循環(huán)中止。根據(jù)循環(huán)不變,每個結點都是最大堆的根。結點1就是最大的那個堆的根。建堆:正確性簡單界:O(n)

調用Max-Heapify,每次調用需要O(lgn)

時間

建堆需要O(nlgn)時間。能找到更準確的界嗎?準確界:

一個結點上Max-Heapify的運行時間是該結點高度的線性函數(shù),大多數(shù)結點的高度很小。堆的高度是(lgn)。最多有

n/2h+1

個高度為h的結點。建堆:分析(1)height3height2height1height0準確界(續(xù)):

最多有

n/2h+1

個高度為h

的結點。在高度為h的結點上運行Max-Heapify的時間是

O(h),因此建堆總的代價是

因為for|x|<1,建堆的代價為O(n)。建堆:分析(1)給定一個數(shù)組,堆排序算法如下:在數(shù)組上建一個最大堆。從根結點開始(它的值最大),算法將最大值放到數(shù)組中正確的地方，也就是將它與數(shù)組中最后一個元素交換位置。“去掉”數(shù)組中最后一個元素(它已經(jīng)在正確的位置)，

在新的根結點上調用Max-Heapify，新的根結點有可能違反堆的性質。重復“去掉”操作直到只剩一個結點(也就是最小值),這是數(shù)組已經(jīng)排序完成。堆排序算法:思想堆排序:偽代碼堆排序:舉例A74312初始數(shù)組:排序后的數(shù)組:Build-Max-Heap:O(n)forloop:n–1次交換值:O(1)Max-Heapify:O(lgn)總時間:O(nlgn)與歸并排序一樣，而且是inplace排序。Heapsort算法分析優(yōu)先隊列堆的應用，實現(xiàn)一個高效的

優(yōu)先隊列。優(yōu)先隊列是一個維護動態(tài)集合

S

數(shù)據(jù)結構，其中每一個元素都有一個值(也稱

key)，這個值表示該元素的優(yōu)先級

。類比最大堆和最小堆，也有最大優(yōu)先隊列

和最小優(yōu)先隊列。最大優(yōu)先隊列的應用:共享計算機系統(tǒng)的作業(yè)調度–在將要執(zhí)行的所有作業(yè)中，選擇優(yōu)先級最高的執(zhí)行。優(yōu)先隊列操作最大優(yōu)先隊列支持如下操作:Insert(S,x):將元素x

插入集合

S。Maximum(S):返回集合

S

中key最大的元素。Extract-Max(S):去掉并返回集合

S

中key最大的元素。Increase-Key(S,x,k):增加元素x

的key到

k。假定

k

x

當前的key。最小優(yōu)先隊列支持的操作：Insert(S,x):將元素x

插入集合

S.Minimum(S):返回集合

S

中key最小的元素.Extract-Min(S):去掉并返回集合

S

中key最小的元素.Decrease-Key(S,x,k):減少元素x

的key到

k。假定

k

≤x

當前的key。用堆實現(xiàn)優(yōu)先隊列的操作用最大堆和它的操作實現(xiàn)最大優(yōu)先隊列。Max-Heap-Insert(A,x)Heap-Maximum(A):returnA[1].Heap-Extract-Max(A,n)Heap-Increase-Key(A,x,k)用最小堆和它的操作實現(xiàn)最小優(yōu)先隊列。Heap-Extract-Max給定數(shù)組A:確保堆不為空。復制最大元素(根結點).把樹中最后一個結點變成新的根結點。重新建立減少一個結點的堆。返回復制的最大元素。時間復雜度：Max-Heapify:

(lgn).Heap-Increase-Key給定數(shù)組A,元素A[i],和新的key:確保key

A[i].更新A[i]的key。向上遍歷樹，比較

A[i]和它的父結點，有需要就交換值,直到

A[i]的key比它的父結點的key小。時間復雜度:O(lgn).Heap-Increase-Key:舉例Heap-Increase-Key(A,i,15)Max-Heap-Insert將key

插入到堆中:增加堆的大小。在堆的最后一個位置增加一個key為–

的結點。增加–

到key

，調用Heap-Increase-Key。時間復雜度:O(lgn).用堆實現(xiàn)優(yōu)先隊列:總結優(yōu)先隊列操作的運行時間

O(lgn).Max-Heap-Insert(A,x):O(lgn)Heap-Maximum(A):returnA[1]:O(1)Heap-Extract-Max(A,n):O(lgn)Heap-Increase-Key(A,x,k):O(lgn)除了Heap-Maximum(A),其他操作的運行時間以堆的高度為界。有些操作向上執(zhí)行。有些操作向下執(zhí)行。優(yōu)先隊列的其他操作假定一個集合S

中，每個元素e有兩個屬性：id:唯一定義epriority:e的優(yōu)先級操作:Find(S,x):在S中找到id=x

元素的優(yōu)先級。ChangePriority(S,x,p):將id=x

元素的優(yōu)先級變?yōu)?/p>

p，可變大，也可變小。問題:用堆實現(xiàn)Find(S,x)的運行時間?答案:O(n),堆中的元素不按id排序。

改進Find(S,x)如何使Find(S,x)的運行時間成為

O(1)？用另一個數(shù)組“handle”追蹤堆中每個元素的位置，如果idx

元素不在堆中，“handle”中的值為“impossiblevalue”。假定:優(yōu)先隊列最多有

n

個元素

id是1至n之間的整數(shù)沒有多次出現(xiàn)的具有相同id的元素改進Find(S,x)(續(xù))引入一個新的數(shù)組L[1..n]追蹤元素的位置:L[i]存儲id=i的元素的位置。兩個數(shù)組

A[1..n]和L[1..n]A[1..n]存儲元素的ids和優(yōu)先級,A[1..n]是堆。L[1..n]存儲A[1..n]中元素的位置。L[1..n]可以在O(1)時間找到任何給定id=x

的元素:該元素是A[L[x]]。如果A中有元素移動，他們的位置也需要在

L

中更新，這是用

O(1)時間實現(xiàn)Find(