《算法設(shè)計與分析》課件 第1章 數(shù)據(jù)結(jié)構(gòu)

算法設(shè)計與分析堆和不相交集數(shù)據(jù)結(jié)構(gòu)算法的實(shí)現(xiàn)離不開數(shù)據(jù)結(jié)構(gòu)。選擇一個合適的數(shù)據(jù)結(jié)構(gòu)對設(shè)計一個有效的算法有十分重要的影響。結(jié)構(gòu)化程序設(shè)計創(chuàng)始人NiklausWirth(瑞士蘇黎士高工)提出一個著名的論斷：“程序=算法+數(shù)據(jù)結(jié)構(gòu)”。1984年，Wirth因開發(fā)了Euler、Pascal等一系列嶄新的計算語言而榮獲圖靈獎,有“結(jié)構(gòu)化程序設(shè)計之父”之美譽(yù)我們已經(jīng)學(xué)過數(shù)組、隊列、棧、二叉樹等數(shù)據(jù)結(jié)構(gòu)，這里學(xué)習(xí)堆和不相交集堆(Heap)在許多算法中，需要大量用到如下兩種操作：插入元素和尋找最大(小)值元素。為了提高這兩種運(yùn)算的效率，必須使用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。普通隊列：易插入元素，但求最大(小)值元素需要搜索整個隊列。排序數(shù)組：易找到最大(小)值，但插入元素需要移動大量元素。堆則是一種有效實(shí)現(xiàn)上述兩種運(yùn)算的簡單數(shù)據(jù)結(jié)構(gòu)。堆(Heap)堆(Heap)：特征堆是一棵完全二叉樹，堆所對應(yīng)樹的節(jié)點(diǎn)的排列必須是從上到下，從左到右的依次排列，否則將不構(gòu)成堆在最大堆中，根節(jié)點(diǎn)值最大，葉子節(jié)點(diǎn)值較小，從根到葉子的一條路徑上，節(jié)點(diǎn)值以非升序排列任何一個父節(jié)點(diǎn)的值都大于等于其子節(jié)點(diǎn)的值，但節(jié)點(diǎn)的左右子節(jié)點(diǎn)值并無順序要求，且上層節(jié)點(diǎn)的值不一定大于下層節(jié)點(diǎn)的值堆中每個結(jié)點(diǎn)的子樹都是堆堆(Heap)有n個節(jié)點(diǎn)的堆T,可以用一個數(shù)組a[1…n]來存儲，按照節(jié)點(diǎn)從上到下，從左到右的順序依次存儲用下面的方式來表示：T的根節(jié)點(diǎn)存儲在a[1]中假設(shè)T的節(jié)點(diǎn)x存儲在a[j]中，那么，它的左右子節(jié)點(diǎn)分別存放在a[2j]及a[2j+1]中(如果有的話)。a[j]的父節(jié)點(diǎn)如果不是根節(jié)點(diǎn)，則存儲在a[

j/2

]中堆(Heap)堆(Heap)：上移若某個節(jié)點(diǎn)a[i]鍵值大于其父節(jié)點(diǎn)的鍵值，就違背了堆的特性，需要進(jìn)行調(diào)整。調(diào)整方法：上移。沿著a[i]到根節(jié)點(diǎn)的唯一一條路徑，將a[i]移動到合適的位置上：比較a[i]及其父節(jié)點(diǎn)a[

i/2

]的鍵值，若key(a[i])>key(a[

i/2

])，則二者進(jìn)行交換，直到a[i]到達(dá)合適位置。堆(Heap)：上移所需要的時間是O(logn).堆(Heap)：下移假如某個內(nèi)部節(jié)點(diǎn)a[i](i≤

n/2

)，其鍵值小于兒子節(jié)點(diǎn)的鍵值,即key(a[i])<key(a[2i])或key(a[i]<key(a[2i+1])(如果右兒子存在)，違背了堆特性，需要進(jìn)行調(diào)整。調(diào)整方法：下移。沿著從a[i]到子節(jié)點(diǎn)(可能不唯一，則取其鍵值較大者)的路徑，比較a[i]與子節(jié)點(diǎn)的鍵值，若key(a[i])<max(a[2i],a[2i+1])則交換之。這一過程直到葉子節(jié)點(diǎn)或滿足堆特性為止。堆(Heap)：下移所需要的時間是O(logn).堆(Heap)：插入思路：先將x添加到a[]的末尾，然后利用Sift-up，調(diào)整x在a[]中的位置，直到滿足堆特性。樹的高度為

logn,所以將一個元素插入大小為n的堆所需要的時間是O(logn).堆(Heap)：刪除思路：先用a[n]取代a[i]，然后對a[i]作Sift-up或Sift-down)，直到滿足堆特性。所需要的時間是O(logn).堆(Heap)：刪除堆頂元素輸入：堆H[1…n]輸出：返回最大鍵值元素，并將其從堆中刪除

x←H[1]2.delete(H,1)3.returnx堆(Heap)：構(gòu)建方法1：從一個空堆開始，逐步插入A中的每個元素，直到A中所有元素都被轉(zhuǎn)移到堆中。時間復(fù)雜度為O(nlogn)因為插入一個元素需要logn，總共需要插入n個元素堆(Heap)：構(gòu)建其他方法：直接對數(shù)據(jù)進(jìn)行調(diào)整自上而下的調(diào)整一次調(diào)整需要O(nlogn)，總共需要log

n次調(diào)整，總復(fù)雜度為O(nlog2n)堆(Heap)：構(gòu)建自下而上的調(diào)整調(diào)整一次即可（對以節(jié)點(diǎn)i為根的子樹進(jìn)行調(diào)整）但復(fù)雜度依然是O(nlogn)優(yōu)化：1.葉子節(jié)點(diǎn)不需要調(diào)整；2.對子樹進(jìn)行調(diào)整第i層的節(jié)點(diǎn)的調(diào)整最多交換?logn??i次堆(Heap)：構(gòu)建例：給定數(shù)組A[1…10]={5,15,19,12,6,10,7,36,11,8，9,16}，構(gòu)建堆堆(Heap)：構(gòu)建堆(Heap)：構(gòu)建復(fù)雜度堆(Heap)：構(gòu)建復(fù)雜度堆(Heap)：d堆d堆：如三叉堆，四叉堆；樹的層數(shù)為logdn不相交集在離散數(shù)學(xué)我們學(xué)過等價類是對集合S的一個劃分，對集合S的劃分形成了集合S的不相交集不相交集不相交集可以用樹表示4個子集1:{1,7,10,11}，3:{2,3,5,6}，8:{4,8}，9:{9}并分別命名。1111072653984不相交集：查找、合并FIND(x):尋找包含元素x的集合的名字記root(x)為包含元素x的樹的根，則FIND(x)返回root(x).UNION(x,y):將包含元素x和y的兩個集合合并，重命名。執(zhí)行合并UNION(x,y)時，首先依據(jù)x找到root(x),記為u,依據(jù)y找到root(y)，記為v；然后，將u指向v。不相交集：查找、合并不相交集：秩和基于秩的合并按秩合并的順序決定了樹的高度。一個有n節(jié)點(diǎn)，且是通過不相交集合并操作形成的樹，其最大的高度是多少？不相交集：秩和基于秩的合并不相交集：秩和基于秩的合并不相交集是不是通過基于秩的合并就總能得到最優(yōu)的不相交集?不一定：如有4個節(jié)點(diǎn)，先合并1和2，再合并3和4，不一定是最優(yōu)的如何優(yōu)化？合并時調(diào)整：復(fù)雜度從O(logn)變?yōu)镺(n)專門設(shè)置一個調(diào)整操作：也為O(n)部分解決方案：路徑壓縮不相交集：路徑壓縮這個算法中為什么不對rank進(jìn)行改變？345例：初始狀態(tài)：{1},{2},…,{9}612789執(zhí)行合并序列：UNION(1,2),UNION(3,4),UNION(5,6),UNION(7,8),得到的結(jié)果是：345612789繼續(xù)執(zhí)行合并序列：UNION(2,4),UNION(8,9),UNION(6,8),得到的結(jié)果是：34