堆排序

概念：

• • 第一個非葉子節(jié)點: 小于size/2的部分;
  • 非葉子節(jié)點的區(qū)間: [0, size/2); (注意是左閉右開)
  • 最大堆:滿足父節(jié)點head, arr[head]<=arr[2*head+1] && arr[head]<=arr[2*head+2]
  • 非葉子節(jié)點的子樹才需要調(diào)整(沒有子節(jié)點的樹何談調(diào)整)?
    ps: 全文使用的下標均是從0開始

堆排序過程

• 初始化堆: 從size/2到0調(diào)整堆, 使得堆滿足條件;
• 調(diào)整堆:?
  如果head在非葉子節(jié)點的區(qū)間, 即head 屬于[0,size/2), 則需要檢查是否需要調(diào)整, 從head, 2head+1, 2head=2中選擇出最大值的下標; 如果maxnIndex!=head, 則需要進行交換swap(arr[head], arr[maxnIndex]), 然后在遞歸檢查以maxnIndex的子樹是否滿足堆的條件(因為在交換后, 子堆可能不滿足堆的條件), 檢查方式adjustHeap(arr,maxnIndex, size);
• 堆排序: 從size-1到1, 逐個與arr[0]交換, 并且重新檢查堆(原來size)-1的堆是否滿足條件: adjustHeap(arr, 0, i);

堆排序代碼

1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 6 void adjustHeap(int arr[], int head, int size){ 7 8 // 如果頭節(jié)點是非葉子節(jié)點才需要進行調(diào)整 9 if(head<size/2){ 10 // 數(shù)組下標從0開始 11 int maxnIndex = head; 12 int left = 2 * head + 1; 13 int right = 2 * head + 2; 14 if(left<size && arr[left]>arr[maxnIndex]) 15 maxnIndex = left; 16 if(right<size && arr[right]>arr[maxnIndex]) 17 maxnIndex = right; 18 if(maxnIndex != head){ 19 swap(arr[head], arr[maxnIndex]); // 將最大值放在頭節(jié)點 20 adjustHeap(arr, maxnIndex, size); // 為了防止調(diào)整后的子樹不滿足堆的條件，需要遞歸調(diào)整 21 } 22 } 23 } 24 25 // 初始化堆 26 void buildHeap(int arr[], int size) { 27 //從第一個非葉子節(jié)點開始調(diào)整堆 28 for(int i=size/2;i>=0;i--){ 29 adjustHeap(arr, i, size); 30 } 31 } 32 33 void headSort(int arr[], int size) { 34 // 建堆 35 buildHeap(arr, size); 36 37 // 堆排序 38 for(int i=size-1;i>0; i--){ 39 swap(arr[0], arr[i]); 40 adjustHeap(arr, 0, i); 41 } 42 } 43 44 int main(){ 45 int arr[1000]; 46 int n; 47 while(cin>>n){ 48 for(int i=0;i<n;i++){ 49 cin >> arr[i]; 50 } 51 52 headSort(arr, n); 53 54 for(int i=0;i<n;i++){ 55 cout << arr[i] << " "; 56 }cout<<endl; 57 } 58 }

?

以下為原理分析部分

堆排序的思想

?

1.堆

??堆實際上是一棵完全二叉樹，其任何一非葉節(jié)點滿足性質(zhì)：

? Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

? 即任何一非葉節(jié)點的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點的關(guān)鍵字。

? 堆分為大頂堆和小頂堆，滿足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱為大頂堆，滿足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱為小頂堆。由上述性質(zhì)可知大頂堆的堆頂?shù)年P(guān)鍵字肯定是所有關(guān)鍵字中最大的，小頂堆的堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的。

2.堆排序的思想

?? 利用大頂堆(小頂堆)堆頂記錄的是最大關(guān)鍵字(最小關(guān)鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)變得簡單。

??? 其基本思想為(大頂堆)：

??? 1)將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無須區(qū)；

??? 2)將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2...n-1]<=R[n];?

??? 3)由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當前無序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換，得到新的無序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復此過程直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成。

??? 操作過程如下：

???? 1)初始化堆：將R[1..n]構(gòu)造為堆；

???? 2)將當前無序區(qū)的堆頂元素R[1]同該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為新的堆。

??? 因此對于堆排序，最重要的兩個操作就是構(gòu)造初始堆和調(diào)整堆，其實構(gòu)造初始堆事實上也是調(diào)整堆的過程，只不過構(gòu)造初始堆是對所有的非葉節(jié)點都進行調(diào)整。

????下面舉例說明：

???? 給定一個整形數(shù)組a[]={16,7,3,20,17,8}，對其進行堆排序。

??? 首先根據(jù)該數(shù)組元素構(gòu)建一個完全二叉樹，得到

?然后需要構(gòu)造初始堆，則從最后一個非葉節(jié)點開始調(diào)整，調(diào)整過程如下：

20和16交換后導致16不滿足堆的性質(zhì)，因此需重新調(diào)整

這樣就得到了初始堆。

即每次調(diào)整都是從父節(jié)點、左孩子節(jié)點、右孩子節(jié)點三者中選擇最大者跟父節(jié)點進行交換(交換之后可能造成被交換的孩子節(jié)點不滿足堆的性質(zhì)，因此每次交換之后要重新對被交換的孩子節(jié)點進行調(diào)整)。有了初始堆之后就可以進行排序了。

此時3位于堆頂不滿堆的性質(zhì)，則需調(diào)整繼續(xù)調(diào)整

這樣整個區(qū)間便已經(jīng)有序了。 從上述過程可知，堆排序其實也是一種選擇排序，是一種樹形選擇排序。只不過直接選擇排序中，為了從R[1...n]中選擇最大記錄，需比較n-1次，然后從R[1...n-2]中選擇最大記錄需比較n-2次。事實上這n-2次比較中有很多已經(jīng)在前面的n-1次比較中已經(jīng)做過，而樹形選擇排序恰好利用樹形的特點保存了部分前面的比較結(jié)果，因此可以減少比較次數(shù)。對于n個關(guān)鍵字序列，最壞情況下每個節(jié)點需比較log2(n)次，因此其最壞情況下時間復雜度為nlogn。堆排序為不穩(wěn)定排序，不適合記錄較少的排序。

轉(zhuǎn)載于:https://www.cnblogs.com/skipping/p/5426737.html

總結(jié)

以上是生活随笔為你收集整理的堆排序总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。