程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 堆排序算法,附圖與C++代碼

堆排序算法,附圖與C++代碼

編輯:C++入門知識

堆的意思就是上面的都比下面大,或者小。

舉個例子,下圖就是個最小堆,父節點都比子節點小。如果將其反過來,父節點都比子節點大,那就是最大堆。

如圖,想象一下東西是怎麼磊成堆的,就能理解這個名字的精妙了。

      1

    /  

  2     7

 /     /

3  4  8  9

堆很容易就可以用數組表示,任意元素i,其子節點就是[2*i],[2*i+1],其父節點就是[j/2],寫起來很簡單吧,也很容易理解。

堆排序的思想就是利用堆的這種父子節點大小關系的特性,來降低比較次數。

想象一下單循環淘汰賽,比如說歐洲冠軍杯。先捉對厮殺,再一層一層往上走。堆排序就是這麼做的。第一次從N中選出冠軍。然後將冠軍拿掉,剩下的N-1再選,以此計算,直到剩最後一個時,全部排序也就完成了。

舉個例子:數組為:2, 5, 3, 2, 3, 0, 8, 1

得到初始狀態如下圖:

       2

     /  

    5     3

   /      /

  2  3  0  8

 /

1

選出第一個冠軍:

       8

     /  

    5     2

   /      /

  2  3  0  3

 /

1

將冠軍移到最後,然後,圖也就變成

       1

     /  

    5     2

   /      /

  2  3  0  3

8

繼續選冠軍:
       5

     /  

    1      3

   /      /

  2  3  0  2

8

再將冠軍移到樹的最後:
       2

     /  

    1      3

   /      /

  2  3  0  5

8

繼續選冠軍:
       3

     /  

    2      3

   /      /

  2  1  0  5

8

再將冠軍移到樹的最後:
       0

     /  

    2     3

   /

  2  1  3  5

8

繼續選冠軍:
       3

     /  

    2     0

   /

  2  1  3  5

8

再將冠軍移到樹的最後:
       1

     /  

    2     0

   /

  2  3  3  5

8

繼續選冠軍:
       2

     /  

    1     0

   /

  2  3  3  5

8

再將冠軍移到樹的最後:
       2

     /  

    1     0

  2  3  3  5

8

繼續選冠軍:
       2

     /  

    1     0

  2  3  3  5

8

再將冠軍移到樹的最後:
       0

     /

    1     2

  2  3  3  5

8

繼續選冠軍:
       1

     /

    0     2

  2  3  3  5

8

再將冠軍移到樹的最後:
       0

    1     2

  2  3  3  5

8

搞定啦!
0, 1, 2, 3, 3, 5, 8
代碼如下:
view plaincopy to clipboardprint?
void FindMaxInHeap(int arr[], const int size) {  
    for (int j = size - 1; j > 0; --j) {  
        int parent = j / 2;  
        int child = j;  
        if (j < size - 1 && arr[j] < arr[j+1]) {  
            ++child;  
        }  
        if (arr[child] > arr[parent]) {  
            int tmp = arr[child];  
            arr[child] = arr[parent];  
            arr[parent] = tmp;  
        }  
    }  
}  
void HeapSort(int arr[], const int size) {  
    for (int j = size; j > 0; --j) {  
        FindMaxInHeap(arr, j);  
        int tmp = arr[0];  
        arr[0] = arr[j - 1];  
        arr[j - 1] = tmp;  
    }  
}  
void TestHeapSort() {  
    int arr[] = {2, 5, 3, 2, 3, 0, 8, 1};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    HeapSort(arr, n);  
    for (int j = 0; j < n; ++j) {  
        cout << arr[j] << ", ";  
    }  
    cout << endl;  

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved