第九章 堆和堆排序

高級(jí)算法設(shè)計(jì)與分析

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

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

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

是樹中所有結(jié)點(diǎn)最大的深度。一個(gè)結(jié)點(diǎn)的高度

=從該結(jié)點(diǎn)到一個(gè)葉子結(jié)點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑的邊數(shù)。一棵樹T的高度

=樹的根結(jié)點(diǎn)的高度=樹的深度二叉樹(2)結(jié)點(diǎn)2的深度=1樹T

的深度=3結(jié)點(diǎn)2的高度=2樹T的高度=3完全二叉樹

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

h的結(jié)點(diǎn)數(shù)？2h+1–1有

n

個(gè)結(jié)點(diǎn)的完全二叉樹的高度?lg(n+1)–1深度為d

的

近似完全二叉樹

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

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

個(gè)結(jié)點(diǎn)的近似完全二叉樹T

的高度是多少?假設(shè)T

不是一個(gè)完全二叉樹。假設(shè)高度是h。T

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

h的結(jié)點(diǎn)，因此,2h–1<n<2h

+1–1

2h≤n<2h

+1

lgn–1<h

≤lgn

h=(lgn)

高度為h

的近似完全二叉樹有多少結(jié)點(diǎn)?假設(shè)有

n

個(gè)結(jié)點(diǎn)，

那么2h≤n<2h

+1

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

近似完全二叉樹

:結(jié)點(diǎn)中存儲(chǔ)的數(shù)值來(lái)自一個(gè)有序的集合。每個(gè)結(jié)點(diǎn)存儲(chǔ)的數(shù)值滿足一種

堆的性質(zhì).兩種堆的性質(zhì):最大堆性質(zhì):每個(gè)結(jié)點(diǎn)存儲(chǔ)的數(shù)值≥該結(jié)點(diǎn)的孩子節(jié)點(diǎn)存儲(chǔ)的數(shù)值。最大值存儲(chǔ)在根結(jié)點(diǎn)最小堆性質(zhì):每個(gè)結(jié)點(diǎn)存儲(chǔ)的數(shù)值

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

最小堆

滿足最小堆性質(zhì)

最大堆舉例

堆(續(xù))如何實(shí)現(xiàn)一個(gè)堆?如果用數(shù)組存儲(chǔ)堆，結(jié)點(diǎn)外的數(shù)字是結(jié)點(diǎn)的數(shù)組下標(biāo)。結(jié)點(diǎn)里的數(shù)字是每個(gè)結(jié)點(diǎn)存儲(chǔ)的值，也叫

keys

。一個(gè)堆可以用一個(gè)數(shù)組A來(lái)實(shí)現(xiàn)。根結(jié)點(diǎn)是

A[1].A[i]的左孩子結(jié)點(diǎn)=A[2i].A[i]的右孩子結(jié)點(diǎn)

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

=A[

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

(n)時(shí)間Heapsort:排序一個(gè)數(shù)組；代價(jià)

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

。

堆的基本操作Max-Heapify

維護(hù)最大堆的性質(zhì)。調(diào)用Max-Heapify之前:A[i],可能比它的孩子結(jié)點(diǎn)小。條件:i

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

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

i

為根的子樹是一個(gè)最大堆。

算法Max-Heapify運(yùn)行時(shí)間:樹的高度是lgn

將

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

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

A[

n/2+1..n]中的元素對(duì)應(yīng)的所有結(jié)點(diǎn)都是葉子結(jié)點(diǎn)。A[

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

n/2]的左孩子是

A[2

n/2]。

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

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

都是一個(gè)最大堆的根結(jié)點(diǎn)。初始化:結(jié)點(diǎn)

n/2+1,

n/2+2,...,n

都是葉子結(jié)點(diǎn),他們都是一個(gè)最大堆的根結(jié)點(diǎn)。

循環(huán)開始時(shí)

i=

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

的孩子結(jié)點(diǎn)的數(shù)組下標(biāo)比i

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

i

成為一個(gè)最大堆的根。遞減

i

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

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

時(shí)間

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

一個(gè)結(jié)點(diǎn)上Max-Heapify的運(yùn)行時(shí)間是該結(jié)點(diǎn)高度的線性函數(shù),大多數(shù)結(jié)點(diǎn)的高度很小。堆的高度是(lgn)。最多有

n/2h+1

個(gè)高度為h的結(jié)點(diǎn)。建堆:分析(1)height3height2height1height0準(zhǔn)確界(續(xù)):

最多有

n/2h+1

個(gè)高度為h

的結(jié)點(diǎn)。在高度為h的結(jié)點(diǎn)上運(yùn)行Max-Heapify的時(shí)間是

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

因?yàn)閒or|x|<1,建堆的代價(jià)為O(n)。建堆:分析(1)給定一個(gè)數(shù)組,堆排序算法如下:在數(shù)組上建一個(gè)最大堆。從根結(jié)點(diǎn)開始(它的值最大),算法將最大值放到數(shù)組中正確的地方，也就是將它與數(shù)組中最后一個(gè)元素交換位置?！叭サ簟睌?shù)組中最后一個(gè)元素(它已經(jīng)在正確的位置)，

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

優(yōu)先隊(duì)列。優(yōu)先隊(duì)列是一個(gè)維護(hù)動(dòng)態(tài)集合

S

數(shù)據(jù)結(jié)構(gòu)，其中每一個(gè)元素都有一個(gè)值(也稱

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

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

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

插入集合

S。Maximum(S):返回集合

S

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

S

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

的key到

k。假定

k

x

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

插入集合

S.Minimum(S):返回集合

S

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

S

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

的key到

k。假定

k

≤x

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

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

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

A[i]和它的父結(jié)點(diǎn)，有需要就交換值,直到

A[i]的key比它的父結(jié)點(diǎn)的key小。時(shí)間復(fù)雜度:O(lgn).Heap-Increase-Key:舉例Heap-Increase-Key(A,i,15)Max-Heap-Insert將key

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

的結(jié)點(diǎn)。增加–

到key

，調(diào)用Heap-Increase-Key。時(shí)間復(fù)雜度:O(lgn).用堆實(shí)現(xiàn)優(yōu)先隊(duì)列:總結(jié)優(yōu)先隊(duì)列操作的運(yùn)行時(shí)間

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),其他操作的運(yùn)行時(shí)間以堆的高度為界。有些操作向上執(zhí)行。有些操作向下執(zhí)行。優(yōu)先隊(duì)列的其他操作假定一個(gè)集合S

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

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

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

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

改進(jìn)Find(S,x)如何使Find(S,x)的運(yùn)行時(shí)間成為

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

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

n

個(gè)元素

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

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

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

L

中更新，這是用

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