閱讀152 返回首頁    go 搜狐

[算法係列之一]堆排序

前序：

(二叉)堆數據結構是一種數組對象，它可以被視為一棵完全二叉樹。樹中每個節點與數組中存放該節點值的那個元素對應。

樹的每一層都是填滿的，最後一層除外。

樹的根為a[1] （在這裏是從1開始的，也可以從0開始），給定了某個節點的下標i，其父節點為i/2，左二子為2*i，右兒子為2*i+1。

二叉堆滿足二個特性：

1．父結點的鍵值總是大於或等於（小於或等於）任何一個子節點的鍵值。

2．每個結點的左子樹和右子樹都是一個二叉堆（最大堆或最小堆）。

當父結點的鍵值總是大於或等於任何一個子節點的鍵值時為最大堆。

當父結點的鍵值總是小於或等於任何一個子節點的鍵值時為最小堆。


保持堆的性質：

MaxHeap是對最大堆進行操作的最重要的子程序。

以i為根的子樹：

在算法每一步中，從a[i], a[Left(i)], a[Right(i)]找出最大值，並將其下標存在LargestIndex中。如果a[i]是最大的，則以i為根的子樹已是最大堆,程序結束。

否則i的某個子結點中有最大元素則交換a[i],a[LargetIndex],從而使i及子女滿足堆性質。下標為LargestIndex的結點在交換後的值為a[i],以該結點為根的子樹又有可能違反最大堆的性質，因而又要對該子樹遞歸調用MaxHeap，重新使子樹平衡。

  1. //調整以index為根的子樹  
  2. //n：堆中元素個數  
  3. int MaxHeap(int a[],int index,int n){  
  4.     int LargestIndex = index;  
  5.     //左子節點  
  6.     int LeftIndex = 2*index;  
  7.     //右子節點  
  8.     int RightIndex = 2*index+1;  
  9.     if(LeftIndex <= n && a[LeftIndex] > a[LargestIndex]){  
  10.         LargestIndex = LeftIndex;  
  11.     }  
  12.     if(RightIndex <= n && a[RightIndex] > a[LargestIndex]){  
  13.         LargestIndex = RightIndex;  
  14.     }  
  15.     //如果a[index]是最大的，則以index為根的子樹已是最大堆否則index的子節點有最大元素  
  16.     //則交換a[index],a[LargetIndex],從而使index及子女滿足堆性質  
  17.     int temp;  
  18.     if(LargestIndex != index){  
  19.         //交換a[index],a[LargetIndex]  
  20.         temp = a[index];  
  21.         a[index] = a[LargestIndex];  
  22.         a[LargestIndex] = temp;  
  23.         //重新調整以LargestIndex為根的子樹  
  24.         MaxHeap(a,LargestIndex,n);  
  25.     }  
  26.     return 0;  
  27. }  

建堆：

我們可以自底向上的用MaxHeap來將一個數組a[1-n]變成一個最大堆，子數組a[n/2+1,........n]中的元素是樹中的葉子，因此每個都可以看做隻含一個元素的堆，滿足最大堆的要求，不用調整。所以隻需調整以a[n/2........1]中元素為根的子樹使之成為最大堆。

  1. //建堆：將一個數組a[1-n]變成一個最大堆  
  2. int BuildMaxHeap(int a[],int n){  
  3.     int i;  
  4.     //子數組a[(n/2+1,n/2+2......n)]中的元素都是樹中的葉子  
  5.     for(i = n/2;i >= 1;i--){  
  6.         //調整以i為根節點的樹使之成為最大堆  
  7.         MaxHeap(a,i,n);  
  8.     }  
  9.     return 0;  
  10. }  

a數組

16 7 3 20 17 8
初始堆：

自底向上從最後一個非葉節點開始調整：

                       （a）                                                    （b）                                                 （c）                                                   （d）

每次調整都是從父節點、左孩子節點、右孩子節點三者中選擇最大者跟父節點進行交換(交換之後可能造成被交換的孩子節點不滿足堆的性質，因此每次交換之後要重新對被交換的孩子節點進行調整)。

堆排序：

開始時，堆排序先用BuildMaxHeap將輸入數組a[1-n]構造成一個最大堆。又因為數組中最大元素在根a[1]，則可以通過它與a[n]交換來達到最終的正確位置。現在，如果從堆中”去掉“結點n(不是真的刪除，而是通過修改堆的元素個數n)，可以很容易的將a[1-(n-1)]建成最大堆。原來根的子女依舊是最大堆，二新交換的根元素很有可能違背最大堆的性質。這時調用MaxHeap重新調整一下。在a[1-(n-1)]中構造出最大堆。堆排序不斷重複這一過程，堆的大小由n-1一直降到2.從而完成排序的功能

  1. //堆排序  
  2. int HeapSort(int a[],int n){  
  3.     int temp;  
  4.     //BulidMaxHeap將輸入數組構造一個最大堆  
  5.     BuildMaxHeap(a,n);  
  6.     //數組中最大元素在根a[1]，則可以通過它與a[n]交換來達到最終的正確位置  
  7.     for(int i = n;i >= 2;i--){  
  8.         //交換  
  9.         temp = a[i];  
  10.         a[i] = a[1];  
  11.         a[1] = temp;  
  12.         //a[i]已達到正確位置，從堆中去掉  
  13.         n--;  
  14.         //重新調整，保持最大堆的性質  
  15.         MaxHeap(a,1,n);  
  16.     }  
  17.     return 0;  
  18. }  



                          （a）                                                   （b）                                               （c）                                                （d）


                        （e）                                                    （f）                                                    （g）


                             （h）                                              （i）                                                  （j）                                                （k）


紅色為排序後的結果；

代碼：

  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3.   
  4. //調整堆  
  5. int MaxHeap(int a[],int index,int n){  
  6.     int LargestIndex = index;  
  7.     //左子節點  
  8.     int LeftIndex = 2*index;  
  9.     //右子節點  
  10.     int RightIndex = 2*index+1;  
  11.     if(LeftIndex <= n && a[LeftIndex] > a[LargestIndex]){  
  12.         LargestIndex = LeftIndex;  
  13.     }  
  14.     if(RightIndex <= n && a[RightIndex] > a[LargestIndex]){  
  15.         LargestIndex = RightIndex;  
  16.     }  
  17.     //如果a[index]是最大的，則以index為根的子樹已是最大堆否則index的子節點有最大元素  
  18.     //則交換a[index],a[LargetIndex],從而使index及子女滿足堆性質  
  19.     int temp;  
  20.     if(LargestIndex != index){  
  21.         //交換a[index],a[LargetIndex]  
  22.         temp = a[index];  
  23.         a[index] = a[LargestIndex];  
  24.         a[LargestIndex] = temp;  
  25.         //重新調整以LargestIndex為根的子樹  
  26.         MaxHeap(a,LargestIndex,n);  
  27.     }  
  28.     return 0;  
  29. }  
  30.   
  31.   
  32. //建堆：將一個數組a[1-n]變成一個最大堆  
  33. int BuildMaxHeap(int a[],int n){  
  34.     int i;  
  35.     //子數組a[(n/2+1,n/2+2......n)]中的元素都是樹中的葉子  
  36.     for(i = n/2;i >= 1;i--){  
  37.         //調整以i為根節點的樹使之成為最大堆  
  38.         MaxHeap(a,i,n);  
  39.     }  
  40.     return 0;  
  41. }  
  42.   
  43. //堆排序  
  44. int HeapSort(int a[],int n){  
  45.     int temp;  
  46.     //BulidMaxHeap將輸入數組構造一個最大堆  
  47.     BuildMaxHeap(a,n);  
  48.     //數組中最大元素在根a[1]，則可以通過它與a[n]交換來達到最終的正確位置  
  49.     for(int i = n;i >= 2;i--){  
  50.         //交換  
  51.         temp = a[i];  
  52.         a[i] = a[1];  
  53.         a[1] = temp;  
  54.         //a[i]已達到正確位置，從堆中去掉  
  55.         n--;  
  56.         //重新調整，保持最大堆的性質  
  57.         MaxHeap(a,1,n);  
  58.     }  
  59.     return 0;  
  60. }  
  61. int main(){  
  62.     int n = 6;  
  63.     //a[0]不用，堆的根結點是從1開始的  
  64.     int a[] = {0,3,17,8,7,16,20};  
  65.     HeapSort(a,n);  
  66.     for(int i = 1;i <= n;i++){  
  67.         printf("%d ",a[i]);  
  68.     }  
  69.     return 0;  
  70. }  

最後更新：2017-04-03 12:56:27

  上一篇：go Wps的ppt裏 讓圖片按順序出現 就是點擊一下 出現一張照片
  下一篇：go Wps的ppt裏 讓圖片按順序出現 就是點擊一下 出現一張照片