第6章堆排序 · 《算法導論》答案

# 一、概念 #### 1.堆heap 堆的本質是一種數組對象，數組下標從1開始堆可以被視作一棵完全二叉樹，二叉樹的層次遍歷結果與數組元素的順序對應，樹根為A[1]。對于數組中第i個元素，其對應在二叉樹中的父母孩子結點位置的計算如下： ``` PARENT(i) return i/2 LEFT(i) return 2i RIGHT(i) return 2i+1 ``` #### 2.最大/小堆(max-heap/min-heap) 從二叉樹的角度看，對于所有非root結點，滿足`node->parent ≥ node`/`node->parent ≤ node` 從數組的角度看，對于所有下標大于1的元素，其下標為i，則滿足`A[PARENT( i)] ≥ A[i]`/`A[PARENT( i)] ≤ A[i]` #### 3.高度height 結點的高度：從結點到葉子所經過的邊的數量，葉子結點的高度為0 二叉樹的高度：樹中高度最高的結點的高度，只有一個結點的樹高度為0 堆的高度：把堆看所作二叉樹時的高度 # 二、程序 #### 1.堆的結構 A[N]：堆數組 length[A]：數組中元素的個數 heap-size[A]：存放在A中的堆的元素個數 #### 2.在堆上的操作（1）MAX-HEAPIFY(A, i) （2）BUILD-MAX-HEAP(A) （3）HEAPSORT(A) #### 3.堆的應用優先級隊列（1）HEAP-MAXIMUM(A) （2）HEAP-INCREASE-KEY(A, i, key) （3）HEAP-EXTRACT-KEY(A) （4）MAX-HEAP-INSERT(A, key) #### 4.堆代碼 [產品代碼](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/src/chapter6/Heap.h) [測試代碼](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/tst/chapter6/HeapTest.cpp) #### 5.排序代碼 [產品代碼](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/src/others/sort.cpp) [測試代碼](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/tst/others/sortTest.cpp) # 三、練習 ### 6.1 堆 ##### 6.1-1 最多2^(h+1) - 1，最少2 ^ h（當樹中只有一個結點時，高度是0） ##### 6.1-2 ``` 上一題結論 ==> 2^h <= n <= 2^(h+1) - 1 ==> h <= lgn <= h + 1 ==> lgn = h ``` ##### 6.1-3 ``` max-heap的定義 ==>A[PARENT(i)]>=A[i] ==>A[1]>A[2],A[3] ==>A[1]>A[4],A[5],A[6],A[7] ==>…… ==>the root of the subtree contains the largest value ``` ##### 6.1-4 葉子上 ##### 6.1-5 是最小堆或最大堆 ##### 6.1-6 不是，7是6的左孩子，但7>6 ##### 6.1-7 ``` A[2i]、A[2i+1]是A[i]的孩子 ==>若2i<=n&&2i+1<=n，則A[i]有孩子 ==>若2i>n，則A[i]是葉子 ==>the leaves are the nodes indexed by ?n/2 ? + 1, ?n/2 ? + 2, . . . , n ``` ### 6.2 保持堆的性質 ##### 6.2-1 A = {27,17,3,16,13,10,1,5,7,12,4,8,9,0} A = {27,17,10,16,13,3,1,5,7,12,4,8,9,0} A = {27,17,10,16,13,9,1,5,7,12,4,8,3,0} ##### 6.2-2 ``` MIN-HEAPIFY(A, i) 1 l <- LEFT(i) 2 r <- RIGHT(i) 3 if l <= heap-size[A] and A[l] < A[i] 4 then smallest <- l 5 else smallest <- i 6 if r <= heap-size[A] and A[r] < [smallest] 7 then smallest <- r 8 if smallest != i 9 then exchange A[i] <-> A[smallest] 10 MIN_HEAPIFY(A, smallest) ``` ##### 6.2-3 沒有效果，程序終止 ##### 6.2-4 i > heap-size[A]/2時，是葉子結點，也沒有效果，程序終止 ##### 6.2-5 我還是比較喜歡用C++，不喜歡用偽代碼 ```c++ void Heap::Max_Heapify(int i) { int l = (LEFT(i)), r = (RIGHT(i)), largest; //選擇i、i的左、i的右三個結點中值最大的結點 if(l <= heap_size && A[l] > A[i]) largest = l; else largest = i; if(r <= heap_size && A[r] > A[largest]) largest = r; //如果根最大，已經滿足堆的條件，函數停止 //否則 while(largest != i) { //根與值最大的結點交互 swap(A[i], A[largest]); //交換可能破壞子樹的堆，重新調整子樹 i = largest; l = (LEFT(i)), r = (RIGHT(i)); //選擇i、i的左、i的右三個結點中值最大的結點 if(l <= heap_size && A[l] > A[i]) largest = l; else largest = i; if(r <= heap_size && A[r] > A[largest]) largest = r; } } ``` ##### 6.2-6 MAX-HEAPIFY中每循環一次，當前處理的結點的高度就會+1，最壞情況下，結點是根結點的時候停止，此時結點高度是logn，因此最壞運行時間是logn ### 6.3 建堆 ##### 6.3-1 ``` A = {5,3,17,10,84,19,6,22,9} A = {5,3,17,22,84,19,6,10,9} A = {5,3,19,22,84,17,6,10,9} A = {5,84,19,22,3,17,6,10,9} A = {84,5,19,22,3,17,6,10,9} A = {84,22,19,5,3,17,6,10,9} A = {84,22,19,10,3,17,6,5,9} ``` ##### 6.3-2 因為MAX-HEAPIFY中使用條件是當前結點的左孩子和右孩子都是堆假設對i執行MAX-HEAPIFY操作，當i=j時循環停止，結果是從i到j的這條路徑上的點滿足最大堆的性質，但是PARENT[i]不一定滿足。甚至有可能在滿足A[PARENT(i)]>A[i]的情況下因為執行了MAX-HEAPIFY(i)而導致A[PARENT(i)]<A[i]，例如下圖，因此一定要先執行MAX-HEAPIFY(i)才能執行MAX-HEAPIFY(PARENT(i)) ![](https://box.kancloud.cn/2016-02-02_56b02bd032fb2.jpg) ##### 6.3-3 對于一個含有n個結點的堆，最多可以有f(h)個葉子結點已知，當h=0時，f(h)=(n+1)/2 高度為h的結點是高度為h-1的結點的父結點，因此f(h) = (f(h-1) + 1) / 2 ``` f(0) = (n + 1) / 2 = 1 + (n-1)/2 f(1) = (f(0) +1) / 2 = 1 + (n-1)/(2^2) f(2) = (f(1) +1) / 2 = 1 + (n-1)/(2^3) …… f(h) = 1 + (n-1) / (2 ^ (h+1)) ``` 因為f(h)必須是整數，所以 ``` f(h) = floor[1 + (n-1) / (2 ^ (h+1)) ] = ceilling[(n-1) / (2 ^ (h+1))] ≤ ceilling[n / (2 ^ (h+1))] ``` 得證：在任一含n個元素的堆中，至多有ceiling(n/(2^(h+1)))個高度為h的節點。參考http://blog.csdn.net/lqh604/article/details/7381893 ### 6.4 堆排序的算法 ##### 6.4-1 A = {5,13,2,25,7,17,20,8,4} A = {25,13,20,8,7,17,2,5,4} A = {4,13,20,8,7,17,2,5,25} A = {20,13,17,8,7,4,2,5,25} A = {5,13,17,8,7,4,2,20,25} A = {17,13,5,8,7,4,2,20,25} A = {2,13,5,8,7,4,17,20,25} A = {13,8,5,2,7,4,17,20,25} A = {4,8,5,2,7,13,17,20,25} A = {8,7,5,2,4,13,17,20,25} A = {4,7,5,2,8,13,17,20,25} A = {7,4,5,2,8,13,17,20,25} A = {2,4,5,7,8,13,17,20,25} A = {5,4,2,7,8,13,17,20,25} A = {2,4,5,7,8,13,17,20,25} A = {4,2,5,7,8,13,17,20,25} A = {2,4,5,7,8,13,17,20,25} A = {2,4,5,7,8,13,17,20,25} ##### 6.4-2 初始化：第一輪迭代之前，i=length[A]，則i=n。顯然，循環不變式成立。保持：每次迭代前，對于一個給定的i。假設循環不變式成立，則子數組A[1..i]是一個包含了A[1..n]中的i個最小元素的最大堆；而子數組A[i+1..n]包含了已排序的A[1..n]中的n-i個最大元素。經過3~5行代碼的操作后，使得子數組A[1..i-1]是一個包含了A[1..n]中的i-1個最小元素的最大堆；子數組A[i..n]包含了已排序的A[1..n]中的n-i+1個最大元素。則可以保證i=i-1后的下一次迭代開始前，循環不變式成立。終止：循環終止時，i=1。根據循環不變式，子數組A[i+1..n]即A[2..n]包含了已排序的A[1..n]中的n-1個最大元素，所以數組A是已排好序的。 ##### 6.4-3 按遞增排序的數組，運行時間是nlgn 按遞減排序的數組，運行時間是n #####6.4-4 堆排序算法中，對堆中每個結點的處理過程為：（1）取下頭結點，O(1) （2）把最后一個結點移到根結點位置，O(1) （3）對該結點執行MAX-HEAPIFY，最壞時間為O(lgn) 對每個結點處理的最壞時間是O(lgn)，每個結點最多處理一次。因此最壞運行時間是O(nlgn) ### 6.5 優先級隊列 ##### 6.5-1 A = {15,13,9,5,12,8,7,4,0,6,2,1} A = {1,13,9,5,12,8,7,4,0,6,2,1} A = {13,1,9,5,12,8,7,4,0,6,2,1} A = {13,12,9,5,1,8,7,4,0,6,2,1} A = {13,12,9,5,6,8,7,4,0,1,2,1} return 15 ##### 6.5-2 A = {15,13,9,5,12,8,7,4,0,6,2,1} A = {15,13,9,5,12,8,7,4,0,6,2,1,-2147483647} A = {15,13,9,5,12,8,7,4,0,6,2,1,10} A = {15,13,9,5,12,10,7,4,0,6,2,1,8} A = {15,13,10,5,12,9,7,4,0,6,2,1,8} ##### 6.5-3 ``` HEAP-MINIMUM(A) 1 return A[1] HEAP-EXTRACR-MIN(A) 1 if heap-size[A] < 1 2 then error "heap underflow" 3 min <- A[1] 4 A[1] <- A[heap-size[A]] 5 heap-size[A] <- heap-size[A] - 1 6 MIN-HEAPIFY(A, 1) 7 return min HEAP-DECREASE-KEY(A, i, key) 1 if key > A[i] 2 then error "new key is smaller than current key" 3 A[i] <- key 4 while i > 1 and A[PARENT(i)] > A[i] 5 do exchange A[i] <-> A[PARENT(i)] 6 i <- PARENT(i) MIN-HEAP-INSERT 1 heap-size[A] <- heap-size[A] + 1 2 A[heap-size[A]] <- 0x7fffffff 3 HEAP-INCREASE-KEY(A, heap-size[A], key) ``` ##### 6.5-4 要想插入成功，key必須大于這個初值。key可能是任意數，因此初值必須是無限小 #####6.5-6 FIFO：以進入隊列的時間作為權值建立最小堆棧：以進入棧的時間作為權值建立最大堆 #####6.5-7 ```c++ void Heap::Heap_Delete(int i) { if(i > heap_size) { cout<<"there's no node i"<<endl; exit(0); } int key = A[heap_size]; heap_size--; if(key > A[i]) //最后一個結點不一定比中間的結點最 Heap_Increase_Key(i, key); else { A[i] = key; Max_Heapify(i); } } ``` ##### 6.5-8 step1：取每個鏈表的第一個元素，構造成一個含有k個元素的堆 step2：把根結點的值記入排序結果中。 step3：判斷根結點所在的鏈表，若該鏈表為空，則go to step4，否則go to step5 step4：刪除根結點，調整堆，go to step2 step5：把根結點替換為原根結點所在鏈表中的第一個元素，調整堆，go to step 2 [產品代碼](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/src/chapter6/Exercise6_5_8.cpp) [測試代碼](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/tst/chapter6/Exercise6_5_8Test.cpp) # 四、思考題 ### 6-1 用插入方法建堆 ```c++ void Heap::Build_Max_Heap() { heap_size = 1; //從堆中最后一個元素開始，依次調整每個結點，使符合堆的性質 for(int i = 2; i <= length; i++) Max_Heap_Insert(A[i]); } ``` 答： a）A = {1,2,3}; b）MAX-HEAP-INSERT的過程如下：加入大小為-0x7FFFFFFF的新結點，O(1) 將該值調整為key,最壞情況下為O(lgn) 對每個結點都要執行一次插入操作，因此最壞時間為O(nlgn) ### 6-2 對d叉堆的分析 a）根結點是A[1]，根結點的孩子是A[2],A[3],……，A[d+1] PARENT(i) = (i - 2 ) / d + 1 CHILD(i, j ) = d * (i - 1) + j + 1 b）lgn/lgd c）HEAP-EXTRACR-MAX(A)與二叉堆的實現相同，其調用的MAX-HEAPIFY(A, i)要做部分更改，時間復雜度是O(lgn/lgd * d) ``` MAX-HEAPIFY(A, i) 1 largest <- i 2 for j <- 1 to d 3 k <- CHILD(i, j) 4 if k <= heap-size[A] and A[k] > A[largest] 5 largest <- k 6 if largest != i 7 then exchange A[i] <-> A[largest] 8 MAX-HEAPIFY(A, largest) ``` d）和二叉堆的實現完全一樣，時間復雜度是O(lgn/lgd) e）和二叉堆的實現完全一樣，時間復雜度是O(lgn/lgd) ### 6-3 Young氏矩陣見[算法導論 6-3 Young氏矩陣](6-3 Young氏矩陣.md)