算法設(shè)計教程ppt課件

1、1,第2章 分治策略,本章主要知識點： 2.1 分治法的基本思想（Divide and Conquer ） 2.2 二分搜索技術(shù) 2.3 大整數(shù)的乘法 2.4 棋盤覆蓋 2.5 歸并排序 2.6 快速排序 2.7 尋找第k小元素 2.8 循環(huán)賽日程表 2.9 補充知識 計劃授課時間：46課時,2,第2章 分治策略,解決問題： 方法1、兩兩比較（最壞情況比8次） 方法2、硬幣分成兩組，一次比較兩組。一次比較后，可以舍棄完全是真幣的那一組，只對另一組進行下一步的比較。（3次） 關(guān)鍵：將大問題分割成若干小問題，小問題與原有問題是完全類似的。,問題：有16枚硬幣，其中有一枚是偽造的，并且那枚偽造硬幣的

2、重量和真硬幣的重量不同(假設(shè)比真幣輕)。你能不能用最少的比較次數(shù)找出這枚偽造的硬幣? 提供一臺可用來比較兩組硬幣重量的儀器,分治法（“分而治之”）。分治法在設(shè)計查找、排序等算法時很有效，最常用的分治法有二分法、歸并法、快速排序等。,3,2.1 分治法的基本思想,分治法的基本思想 大問題分解為子問題，這些子問題互相獨立且與原問題相同。 分別求解子問題。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。 合并解，自底向上逐步求出原來問題的解。 分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而

3、治之。,4,2.1 分治法的基本思想,分治法的適用條件 分治法所能解決的問題一般具有以下幾個特征： 該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 ） 利用該問題分解出的子問題的解可以合并為該問題的解； 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。,5,2.1 分治法的基本思想,分治法的基本步驟 divide

4、-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk；/分解問題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問題 return merge(y1,.,yk); /將各子問題的解合并為原問題的解 ,6,2.1 分治法的基本思想,人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一

5、種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。,7,2.1 分治法的基本思想,分治法的復(fù)雜性分析 分治法將規(guī)模為n的問題分成k個規(guī)模為nm的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有（右上）。 通過迭代法求得方程解（右下） 。,注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)

6、的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時，T(mi)T(n)T(mi+1)。,8,補充：遞歸方程求解,常用方法： 代入法 迭代法 套用公式法 差分方程法 母函數(shù)法,9,補充：遞歸方程求解,1、代入法 先推測遞歸方程的顯式解，然后用數(shù)學(xué)歸納法證明這一推測的正確性。那么，顯式解的漸近階即為所求。 例如：,10,補充：遞歸方程求解,2、迭代法 通過反復(fù)迭代，將遞歸方程的右端變換成一個級數(shù)，然后求級數(shù)的和，再估計和的漸近階 。另外可畫遞歸樹。,2.5 歸并排序,11,補充：遞歸方程求解,T(n)=2*T(n/2) + O(n) =2*（2*T(n/4) + 2*O(n/2) +

7、 O(n) =4*T(n/4) + 2*O(n) =8*T(n/8) + 3*O(n) . =2k * T(n/ 2k) + k*O(n) 令 (n=2k, k=log(n) (注：log(n)是以為底） 則原式T(n)等于 =n*T(1)+ log(n)*O(n) =n*O(1)+ O(n*log(n) =O(n) + O(n*log(n) =O(n*log(n),12,遞歸樹,T(n)= T(n/3)+ T(2n/3)+n 當(dāng)我們累計遞歸樹各層的值時，得到每一層的和都等于n，從根到葉的最長路徑是,先按橫向求出每層結(jié)點的值之和，并記錄在各相應(yīng)層右端頂格處，然后從根到葉逐層地將頂格處的結(jié)果加起

8、來便是我們要求的結(jié)果。,13,補充：遞歸方程求解,3、套用公式法 對于形如 T(n)=aT(n/b)+f(n) 的遞歸方程，給出三種情況下方程解的漸近階的三個相應(yīng)估計公式供套用。,14,補充：遞歸方程求解,3、套用公式法,4、差分方程法 有些遞歸方程可以看成一個差分方程，因而可以用解差分方程(初值問題)的方法來解遞歸方程,5、母函數(shù)法,15,2.2 二分搜索技術(shù),給定已按升序排好序的n個元素a1:n，現(xiàn)要在這n個元素中找出一特定元素x。 適用分治法求解問題的基本特征： 該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個規(guī)模較小的相同問題; 分解出的子問題的解可以合并為原問題

9、的解； 分解出的各個子問題是相互獨立的。 很顯然此問題分解出的子問題相互獨立，即在ai的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。,16,二分檢索原理,將二分檢索問題問題表示為：I=(n, a1, , an, x) 選取一個下標(biāo)k，可得到三個子問題： I1=(k-1, a1, , ak-1, x) I2=(1, ak , x) I3=(n-k, ak+1, , an, x),2.2 二分搜索技術(shù),17,2.2 二分搜索技術(shù),問題描述 已知一個按非降次序排列的元素表a1,a2,an，判定某個給定元素x是否在該表中出現(xiàn)，若是，則找出該元素在表中的位置，并置于j，否則，置j為0

10、。 一般解決方法（從頭到尾查找一遍）,x,成功和不成功最壞情況下需要O（n）次比較,18,二分搜索算法： public static int binarySearch(int a, int x, int n) / 在 a0 amid) left = mid + 1; else right = mid - 1; return -1; / 未找到x ,思考：二分搜索查找遞歸算法？,2.2 二分搜索技術(shù),19,/初始 left = 0; right = N - 1; public static int binarySearch(int a, int x, int left ,int right) /

11、 找到x時返回其在數(shù)組中的位置，否則返回-1 if (leftright) return -1;/ 未找到x else int mid = (left + right)/2; if (x = amid) return mid; if (x amid) return binarySearch(a, x, mid+1,right); else return binarySearch( a,x,left,mid-1); ,思考：二分搜索查找遞歸算法,2.2 二分搜索技術(shù),20,二分檢索算法所需的空間和時間,所需空間: 用n個位置存放數(shù)組A，還有l(wèi)ow, high, mid, x, j五個變量需要存儲

12、，共需空間 n+5,所需計算空間: 對于計算時間，需要分別考慮以下幾種情況： 成功檢索的最好情況、平均情況、最壞情況 不成功檢索的最好情況、平均情況、最壞情況,2.2 二分搜索技術(shù),21,二分檢索的時間復(fù)雜度,定理: 若n在區(qū)域（2k-1, 2k中，則對于一次成功的檢索，二分檢索算法至多作k次比較（即logn）。,22,2.3 大整數(shù)的乘法,設(shè)計一個有效的算法，可以進行兩個n位大整數(shù)的乘法運算 小學(xué)的方法：O(n2) 效率太低 分治法: X=A10n/2+B Y=C10n/2+D XY=AC10n+(AD+BC)10n/2+BD 復(fù)雜度分析 T(n)=O(n2) 沒有改進,23,算法改進,為了

13、降低時間復(fù)雜度，必須減少乘法的次數(shù)。為此，我們把XY寫成另外的形式： XY = AC 10n + (A-C)(B-D)+AC+BD) 10n/2 + BD 或 XY = AC 10n + (A+C)(B+D)-AC-BD) 10n/2 + BD 復(fù)雜性： 這兩個算式看起來更復(fù)雜一些，但它們僅需要3次n/2位乘法AC、BD和(AC)(BD)，于是 T(n)=O(nlog3) =O(n1.59) 較大的改進 細(xì)節(jié)問題：兩個XY的復(fù)雜度都是O(nlog3)，但考慮到A+C ,B+D 可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。,24,參考代碼,void main() long x,

14、y,a,b,c,d; double z; coutxy; a=x/(long)pow(10,num_len(x)/2); b=x%(long)pow(10,num_len(x)/2); c=y/(long)pow(10,num_len(y)/2); d=y%(long)pow(10,num_len(y)/2); /z=(double)(a*c*pow(10,num_len(x)+(a*d+b*c)*pow(10,num_len(x)/2)+b*d); z=(double)(a*c*(long)pow(10,num_len(x)+(a-c)*(b-d)+a*c+b*d)*(long)pow(10

15、,num_len(x)/2)+b*d); coutthe result is z; ,25,參考代碼（續(xù)上頁）,int num_len(long z) int t=0; while(z0) z=z/10; t+; return t; ,26,更快的方法,小學(xué)的方法：O(n2)效率太低 分治法: O(n1.59)較大的改進 更快的方法？ 如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。 最終的，這個思想導(dǎo)致了快速傅利葉變換(Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個復(fù)雜的分治算法，對于大整數(shù)乘法，它能在O(nlogn)時間內(nèi)解決。

16、是否能找到線性時間的算法？目前為止還沒有結(jié)果。,27,2.4 棋盤覆蓋,在一個2k2k個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。 易知，覆蓋任意一個2k2k的特殊棋盤，用到的骨牌數(shù)恰好為(2k2k -1)/3。,28,2.4 棋盤覆蓋,分治策略算法描述 當(dāng)k0時，將2k2k棋盤分割為4個2k-12k-1 子棋盤如圖(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。 將3個無特殊方格的子棋盤轉(zhuǎn)

17、化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如圖(b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。 遞歸地使用這種分割， 直至棋盤簡化為棋盤11。,29,2.5 歸并排序,基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。,Step1： 把待排序的n個記錄看作長度為1的有序序列。將相鄰子序列兩兩歸并為長度為2或1的有序序列； Step2 ：把得到的n/2個長度為2的有序子序列再歸并為長度為 2*2 的有序序列； Step3 ：按Step2的方式，重復(fù)對相鄰有序子序列進行歸并操作，直到成為一個有

18、序序列為止。,30,2.5 歸并排序,算法mergeSort 初始序列 49 38 65 97 76 13 27 第一步 38 49 65 97 13 76 27 第二步 38 49 65 97 13 27 76 第三步 13 27 38 49 65 76 97,動畫演示：,2.5 歸并排序,遞歸算法描述： void merge_sort(int data, int left, int right) if(left right) int mid = (left+ right) / 2; merge_sort(data, left, mid); merge_sort(data, mid+1, r

19、ight); merge(data, left, mid, right); ,初始序列8 4 5 6 2 1 7 3歸并到b 4 8 5 6 1 2 3 7復(fù)制到a 4 8 5 6 1 2 3 7歸并到b 4 5 6 8 1 2 3 7復(fù)制到a 4 5 6 8 1 2 3 7歸并到b 1 2 3 4 5 6 7 8復(fù)制到a 1 2 3 4 5 6 7 8,void merge(int array, int p, int q, int r) int i,k;int begin1,end1,begin2,end2; int* temp = new int r-p+1; /申請空間，使其大小為兩個已

20、經(jīng)排序序列之和，該空間用來存放合并后的序列 /設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起止位置 begin1= p; end1 = q; begin2 = q+1; end2 = r; k = 0; while(begin1 = end1) ,/接上頁 /若第一個序列有剩余，拷貝出來粘到合并序列尾 while(begin1=end1) tempk+ = arraybegin1+; /若第二個序列有剩余，拷貝出來粘到合并序列尾 while(begin2=end2) tempk+ = arraybegin2+; for (i = 0; i (r - p +1); i+) /將排序好的序列拷貝

21、回數(shù)組中 arrayp+i = tempi; delete (temp); ,34,2.5 歸并排序,復(fù)雜度分析 T(n)=O(nlogn) 漸進意義下的最優(yōu)算法,35,2.5 歸并排序,T(n)=2*T(n/2) + O(n) =2*（2*T(n/4) + 2*O(n/2) + O(n) =4*T(n/4) + 2*O(n) =8*T(n/8) + 3*O(n) . =2k * T(n/ 2k) + k*O(n) 令 (n=2k, k=log(n) (注：log(n)是以為底） 則原式T(n)等于 =n*T(1)+ log(n)*O(n) =n*O(1)+ O(n*log(n) =O(n)

22、+ O(n*log(n) =O(n*log(n),36,2.5 歸并排序,在歸并排序算法中，算法總的時間復(fù)雜度為O(nlog2n)。 歸并排序占用附加存儲較多，需要另外一個與原待排序記錄數(shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。 與快速排序和堆排序相比，歸并排序的最大特點是，它是一種穩(wěn)定的排序方法。,37,2.6 快速排序,快速排序是對起泡（冒泡）排序的一種改進方法，它是由C.A.R. Hoare于1962年提出的。,38,起泡排序,起泡排序基本思想： 設(shè)數(shù)組a中存放了n個數(shù)據(jù)元素，循環(huán)進行n-1趟如下的排序過程：,依次比較相臨兩個數(shù)據(jù)元素，若aiai+1，則交換兩個數(shù)據(jù)元素，否則不交換。,

23、當(dāng)完成一趟交換以后，最大的元素將會出現(xiàn)在數(shù)組的最后一個位置。,依次重復(fù)以上過程，當(dāng)?shù)趎-1趟結(jié)束時，整個n個數(shù)據(jù)元素集合中次小的數(shù)據(jù)元素將被放置在a1中，a0中放置了最小的數(shù)據(jù)元素。,39,起泡排序,49,38,65,97,76,13,27,97,97,97,38,49,27,13,76,65,38,49,27,65,13,38,49,27,13,38,49,27,13,38,27,13,76,76,65,49,38,27,13,特點： 1.n個數(shù)排序共需進行n-1趟比較 2.第i趟共需要進行n-i次比較,40,起泡排序的原始算法,/ 將a中整數(shù)序列排列成自小至大有序的序列void bubbl

24、f_sort(array a) for(i=1,iaj+1) aj aj;,假設(shè)array.length=n，則總共比較n2次,41,最壞情況（反序）：,最好情況（正序）：,時間復(fù)雜度為O(n)；,時間復(fù)雜度為O(n2)。,平均情況：時間復(fù)雜度為O(n2)。,時間性能分析,42,2.6 快速排序,基本思想 通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。,動畫演示：,43,快速排序,49 38 65 97 76 13 27 69,27,65,1

25、3,97,49,第一趟結(jié)果： 27 38 13 49 76 97 65 69 ,小于49,大于等于49,44,2.6 快速排序,算法過程： 指定樞軸(通常為第一個記錄) 通過一趟排序?qū)⒁詷休S為中心，把待排記錄分割為獨立的兩部分，使得左邊記錄的關(guān)鍵字小于樞軸值，右邊記錄的關(guān)鍵字大于樞軸值 對左右兩部分記錄序列重復(fù)上述過程，依次類推，直到子序列中只剩下一個記錄或不含記錄為止。,45,2.6 快速排序,一趟快速排序的算法是： 1）設(shè)置兩個變量left、right，排序開始時：left=0，right=N-1； 2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，s=number0； 3）從right開始向前搜索，即由

26、后開始向前搜索（right-），找到第一個=s的值 5）交換Aleft,Aright 6）重復(fù)第3-5步，直到 left=right,46,2.6 快速排序,算法步驟： （1）分解(Divide)：將輸入的序列numberleft.right劃分成兩個非空子序列number left.q和number q+1.right，使number left.q中任一元素的值不大于number q+1.right中任一元素的值。 （2）遞歸求解(Conquer)：通過遞歸調(diào)用快速排序算法分別對number left.q和number q+1.right進行排序。 （3）合并(Merge)：由于對分解出的兩

27、個子序列的排序是就地進行的，所以在number left.q和number q+1.right都排好序后不需要執(zhí)行任何計算number left.right就已排好序。,47,2.6 快速排序,void quicksort(int number, int left, int right) int q; if(left right) q=partition(number, left, right); /分解 quicksort(number, left, q-1); /排序 quicksort(number, q+1, right); ,int partition(int number, int

28、 left, int right) int s; s = numberleft; while(lefts) right-; while(numberlefts) left+; SWAP(numberleft, numberright); numberleft=s; / 樞軸記錄到位 return left; / 返回樞軸位置 ,#define MAX 10 #define SWAP(x,y) int t; t = x; x = y; y = t; void main() int numberMAX = 0; int i; srand(time(NULL); cout排序前：; for(i =

29、0; i MAX; i+) numberi = rand() % 100; coutsetw(6)numberi; quicksort(number, 0, MAX-1); coutn排序后：; for(i = 0; i MAX; i+) coutsetw(6)numberi; coutn; ,50,2.6 快速排序,對于n個成員，快速排序法的比較次數(shù)大約為n*logn 次，交換次數(shù)大約為(n*logn)/6次。如果n為100，冒泡法需要進行4950 次比較，而快速排序法僅需要200 次。快速排序法的性能與中間值的選定關(guān)系密切，如果每一次選擇的中間值都是最大值（或最小值），該算法的速度就會大大

30、下降。 快速排序算法最壞情況下的時間復(fù)雜度為O(n2)，而平均時間復(fù)雜度為O(n*logn),51,尋找支點元素sel_有多種實現(xiàn)方法，不同的實現(xiàn)方法會導(dǎo)致快速排序的不同性能。 根據(jù)分治法平衡子問題的思想，我們希望支點元素可以使aleft.right盡量平均地分為兩部分。 幾種尋找pivot的方法(見補充快速排序文件)： aleft.right 選擇的第一個元素aleft的值作為p(代碼3)； 選擇最后一個元素aright的值作為p (代碼1) ； 選擇中間位置的元素amid的值作為p (代碼2) ； 選擇aleft.right的某一個隨機位置上的值作為p；,分解/劃分算法描述,52,（略）2

31、.7 尋找第k小元素,元素選擇問題：給定線性序集中n個元素和一個整數(shù)k，1kn，要求找出這n個元素中第k小的元素。 Randomized_Select算法：模仿快速排序算法，首先對輸入數(shù)組進行劃分，然后對劃分出的子數(shù)組之一進行遞歸處理。,53,（略）2.7 尋找第k小元素,int RANDOMIZED_SELECT(int arrLEN,int p,int r,int i) /找到arr中第i小的數(shù)，數(shù)組下標(biāo)從1開始 if(p=r) return arrp; int q = RANDOMIZED_PARTITION(arr,p,r); int k = q-p+1; if(i=k) return

32、 arrq; else if(ik) return RANDOMIZED_SELECT(arr,p,q-1,i); else return RANDOMIZED_SELECT(arr,q+1,r,i-k); ,54,（略） 2.7 尋找第k小元素,算法復(fù)雜性：在最壞情況下，算法randomized_Select需要O(n2)計算時間。 可以證明，算法Randomized_Select可以在O(n)平均時間內(nèi)找出n個輸入元素中的第k小元素。,55,2.8 循環(huán)賽日程表,分治法不僅可以用來設(shè)計算法，而且再其他方面也有廣泛應(yīng)用：利用分治法設(shè)計電路、構(gòu)造數(shù)學(xué)證明等。 循環(huán)賽日程標(biāo)問題，設(shè)有n=2k個選

33、手要進行循環(huán)賽，設(shè)計一個滿足以下要求的比賽日程表： 每個選手必須與其他n-1個選手各賽一次； 每個選手一天只能賽一次； 循環(huán)賽一共進行n-1天。 按此要求，可以將比賽日程表設(shè)計成n行n-1列的表格，i行j列表示第i個選手在第j天所遇到的選手。 基本思路：按分治策略，將所有的選手分為兩組，n個選手的比賽日程表就可以通過為n/2個選手設(shè)計的比賽日程表來決定。遞歸地用對選手進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這2個選手進行比賽就可以了。,56,2.8 循環(huán)賽日程表,以k=3(即N=23=8)為例，可以根據(jù)問題要求，制定出如下圖所示的一種方案： 以表格的中心為拆分點

34、，將表格分成A、B、C、D四個部分，就很容易看出有A=D，B=C，并且，這一規(guī)律同樣適用于各個更小的部分。,57,2.8 循環(huán)賽日程表,這樣，對8個隊的賽事排列就逐步減化為對4個隊的排列，然后又進一步減化為對2個隊的排列，最 后就成為1個隊的排列。因此，這一問題可以采用分治法的思想來解決。 在設(shè)計程序時，采用由小到大的方法進行擴展，而數(shù)組下標(biāo)的處理是解決該問題的關(guān)鍵。,思考：若n為奇數(shù)，例如5，應(yīng)該如何排？,58,補充知識一：堆排序,一、堆（heap）的概念 特殊的二叉樹結(jié)構(gòu)，是一個從上到下有大小關(guān)系的二叉樹。 （如父節(jié)點=子節(jié)點 或者 父節(jié)點=子節(jié)點） 其中，父節(jié)點值大于或等于其孩子節(jié)點值的

35、，叫“最大堆（maximum heap)”;父節(jié)點值小于或等于孩子節(jié)點值的，叫“最小堆（minimum heap)”.,在最大堆中，根中的元素值最大； 在最小堆中，根中的元素值最小。,59,補充知識一：堆排序,在起始索引為 0 的“堆”中：1) 堆的根節(jié)點將存放在位置 0 2) 節(jié)點 i 的左子節(jié)點在位置 2 * i + 13) 節(jié)點 i 的右子節(jié)點在位置 2 * i + 24) 節(jié)點 i 的父節(jié)點在位置 floor( (i - 1) / 2 ) : 注 floor 表示“取整”操作 在起始索引為 1 的“堆”中：1) 堆的根節(jié)點將存放在位置 12) 節(jié)點 i 的左子節(jié)點在位置 2 * i3)

36、 節(jié)點 i 的右子節(jié)點在位置 2 * i + 14) 節(jié)點 i 的父節(jié)點在位置 floor( i / 2 ) : 注 floor 表示“取整”操作,60,補充知識一：堆排序,二、堆的存儲 按某種次序?qū)⒁幌盗袛?shù)據(jù)以完全二叉樹形式存放的一種表。它要求堆中的節(jié)點的值都（或）其孩子節(jié)點的值。 lengthA：數(shù)組元素個數(shù)。 heap_sizeA：存放在數(shù)組A中的堆的元素個數(shù)。 例如： 12, 39, 20, 65, 47, 34, 98, 81, 73, 56為“小頂堆”； 98, 81, 34, 73, 56, 12, 20, 39, 65, 47為大頂堆。,parent(i): left（i）：2

37、i right(i):2i+1,61,補充知識一：堆排序,三、堆化 數(shù)組具有對應(yīng)的樹表示形式。一般情況下，樹并不滿足堆的條件。通過重新排列元素，可以建立一棵“堆化”的樹。,heapify(A,i) /示例最大堆化 lleft(i) /左子節(jié)點 r right(i) /右子節(jié)點 if lAi then largest l else largest i if rAlargest then largest r if largest i then exchange (Ai,Alargest) heapify(A,largest),62,補充知識一：堆排序,例如物理結(jié)構(gòu)： 15，35，25，30，40，

38、50,60,12,8,31,36 從i=2處堆化。,原始邏輯結(jié)構(gòu)： 15 / 35 25 / / 30 40 50 60 / / 12 8 31 36,63,補充知識一：堆排序,Build-heap(A) /建堆，起始索引1 heap-sizeAlengthA for ifloor(lengthA /2) downto 1 do heapify(A,i),四、建堆的過程是一個從下到上調(diào)整堆的過程,例如：A(4,1,3,2,16,9,10,14,8,7)，學(xué)生演示其建最大堆過程,用floor(lengthA /2)求出最后一個有兒子的節(jié)點,64,補充知識一：堆排序,堆排序方法基本思想：將原始記錄

39、序列建成一個堆，稱之為初始堆，并輸出堆頂元素；調(diào)整剩余的記錄序列，使之成為一個新堆，再輸出堆頂元素；依此類推，當(dāng)堆中只有一個元素時，整個序列的排序結(jié)束，輸出的序列便是 原始序列的排序序列。,HeapSort(A，int n) 對記錄序列A1.n進行堆排序。 Build-heap(A); for(i=n;i1;i-) A1Ai; 將堆頂記錄和當(dāng)前未經(jīng)排序子序列A1.i中最后一個記錄相互交換 heap-sizeA heap-sizeA -1 heapify(A); ,例如：A=5,13,2,25,7,17,20,8,4 堆排序后,A=2,4,5,7,8,13,17,20,25,65,補充知識一：堆

40、排序,五、堆的應(yīng)用-優(yōu)先級隊列 （priority queue） 概念：用來維護由一組元素構(gòu)成的集合S的數(shù)據(jù)結(jié)構(gòu)，每一個元素都有一個關(guān)鍵字key。數(shù)據(jù)項按關(guān)鍵字的值有序，關(guān)鍵字最小的數(shù)據(jù)項（或者在某些實現(xiàn)中是關(guān)鍵字最大的數(shù)據(jù)項）總是在隊頭。數(shù)據(jù)項插入的時候會按照順序插入到合適的位置以確保隊列的順序。討論基于最大堆的最大優(yōu)先級隊列 應(yīng)用：分時計算機作業(yè)調(diào)度,66,補充知識一：堆排序,操作： max (S):返回S中具有最大關(guān)鍵字的元素 insert(S,x):將x插入S extract-max(S):去掉最大，從余下的選出最優(yōu),HEAP- max (A) 1. return A1 O(1),67

41、,補充知識一：堆排序,HEAP-extract- max(A) if heap-sizeA1 then error “heap underflow” maxA1 A1 Aheap-sizeA /最后一個元素放在第一 heap-sizeA heap-sizeA -1 heapify(A,1); return max,O(1) O(1) O(1) O(1) O(nlog(n-1) O(1) 總計O(nlogn),68,補充知識一：堆排序,HEAP-insert(A,key) /將key插入最大堆A中 heap-sizeA heap-sizeA +1 i heap-sizeA while i1 an

42、d Aparent(i)key do aiAparent(i) i parent(i) Ai key,O(1) O(1) O(logn) O(1)* O(logn) O(1)* O(logn) O(1) 總計O(logn),原始邏輯結(jié)構(gòu)如下，插入35 65 / 45 25 / / 30 40 15 10 / / 12 8 31 36,69,補充知識二：線性時間排序,1、計數(shù)排序-Count Sort 集合A有n個元素，每一個元素的值是介于0到k之間的整數(shù)。 輸入：A1.n 存放排序結(jié)果：B1.n 臨時存儲： C0.k 計數(shù)排序的基本思想是對每一個輸入元素x，確定出小于x的元素個數(shù)。有了這一信息

43、，就可以把x直接放到它在最終輸出數(shù)組 的位置上。例如：若有5個元素小于x，則x就屬于第6個輸出位置 。,70,補充知識二：線性時間排序,1、計數(shù)排序-Count Sort 例如：A=3,6,4,1,3,4,1,4,數(shù)值從1-6,將A從右往左讀，第一個數(shù)為4，查C表為7，生成排序后B數(shù)組,練習(xí)： A=1,3,2,4,7,5,2,1,3,6,求排序后數(shù)組B,71,補充知識二：線性時間排序,Count-Sort(A,B,k) /0=ai=k for i0 to k do Ci 0 for j 1 to lengthA do CAj CAj +1 for i 1 to k do Ci Ci +Ci-1 for jleng