累堆排序法 (Heap Sort)

從樹狀結構來看時，原資料是位在最低層(0層)而最高層的資料才是每一循環所要的。 如果原資料個數不多，資料從最低層到最高層的移動並不會影響排序效率太大， 但資料若很多時，或者是排序後面的幾次循環含有不必要的動作時，則排序效率則大受影響； 為了解決這個缺點，我們使用累堆排序(Heap Sort)法。

定義 累堆排序成功的減少選擇排序法的比對次數，是由John Williams所提出 利用二元樹的技巧，使每一筆資料的比對次數，不會大於logn的值，所以它的時間複雜度和快速排序法相同皆為O(nlogn)，而且它不須任何多餘的記憶空間，它沒有使用到遞迴的函數呼叫。 累堆排序法首先將所有的資料排成一棵累堆樹(heap tree)

累堆樹的形成 它是一個完整二元樹； 所有子樹的根節點值均大於其左右子節點的值。 假設a[ ]資料有12，55，618，40，60，47，25，1，30，6，66；將它表示成完整二元樹如圖

12 55 618 40 60 47 25 1 30 6 66 完整二元樹  

將它調整成累堆樹，調整步驟如下： 令節點i為最後一個非終端節點：N為資料總量 節點j為節點i的左右子節點中較大者： if ( a[ 2*i + 1 ] > a [2 * i +2] ) j = 2 * i + 1 ; else j = 2 * i + 2 ; 如果節點i資料值小於節點j的資料值，則節點i、j交換，並且將i 值設為j值： if ( a[ i ] > a [ j ] ) swap ( a [i ] , a [ j ] ) ; i =j ; 如果節點i還有子節點則回到step 2 如果i大於0，則i = i –1，回到step 2

(a) 60與66交換 12 55 618 40 66 47 25 1 30 6 60

(b)55與66交換後，再與60交換 12 66 618 40 60 47 25 1 30 6 55

(c) 12與618交換後，再與47交換 618 66 47 40 60 12 25 1 30 6 55

基本運算 累堆樹由小至大排序的過程

(a) 618與55交換 55 66 47 40 60 12 25 1 30 6 a[ ] 1 2 3 4 5 6 7 8 9 10 值 55 66 47 40 60 12 25 30 618 排序完成

(b)調整55 66 60 47 40 55 12 25 1 30 6 a[ ] 1 2 3 4 5 6 7 8 9 值 66 60 47 40 55 12 25 30

(c) 66與6交換，調整6 60 55 47 40 6 12 25 1 30 a[ ] 1 2 3 4 5 6 7 8 9 值 60 55 47 40 12 25 30 66 排序完成

(d)66和30交換，調整30 55 40 47 30 6 12 25 1 a[ ] 1 2 3 4 5 6 7 8 值 55 40 47 30 12 25 60 排序完成

(e) 55與1交換，調整1 47 40 25 30 6 12 1 a[ ] 1 2 3 4 5 6 7 值 47 40 25 30 12 55 排序完成 

(f)47和1交換，調整1 40 30 25 1 6 12 a[ ] 1 2 3 4 5 6 值 40 30 25 12 47 排序完成

(g) 40與12交換，調整12 30 12 25 1 6 a[ ] 1 2 3 4  5 值 30 12 25 6  40 排序完成

(h)6和30交換，調整6 25 12 6 1 a[ ] 1 2 3 4 值 25 12 6 30 排序完成

(i) 25與1交換，調整1 12 1 6 a[ ] 1 2 3 值 12 6 25 排序完成

(j)12和6交換 6 1 a[ ] 1 2 值 6 排序完成

演算法 ＝＞C語言程式碼 move_down(int a[ ], int from, int to) { int i, j, t ; i = from ; while ( i < to /2 ) j = i * 2 + 1 ; if ( j + 1 < to && a [ j ] < a [ j +1 ] ) j + + ; if (a [ i ] < a [ j ] )

{ t = a [ i ] ; a [ i ] = a [ j ] ; a [ j ] = t ; } i = j ;

heap_sort(int a[ ], int n ) { int i, t ; for ( i = n /2 – 1 ; i >= 0 ; i - -) ; move_down(a, i, n) ; for ( i = n – 1 ; i > 0 ; i - -) ; t = a [ 0] ; a [ 0 ] = a [ i ] ; a [ i ] = t ; move_down ( a, 0, i ) ; }

＝＞時間複雜度分析 累堆排序是不穩定的情況， 其最壞與平均的時間複雜度均為O(nlogn)。 所需的額外空間很少。

程式範例－累堆排序 #include <studio.h> void adjust ( int [ ], int ) ; int data [11] = {0, 75, 23, 98, 44, 57, 12, 29, 64, 38, 82 } ; void main ( ) { int i , k , temp ; printf ( “\n << Heap sort >>\n ) ; printf ( “Number : “ ) for ( k = 1; k <= 10; k ++) printf ( “%d “, data [k] ); puts (“ “);for ( k = 0; k < 60; k ++) printf ( “-“ ) ;

for ( i = 10 / 2 ; i > 0 ; i --) adjust ( i, 10 ) ; printf ( “\nHeap : “ ) ; for ( k = 1; k <= 10; k ++) printf ( “%d “, data [k] ) ; for ( i = 9; i > 0; i --) { temp = data [i+1] ; data [i+1] = data [1] ;

data [1] = temp ; adjust (1, i ); printf ( “\nAccess : “) ; for ( k = 1; k < 60; k ++) printf ( “%d “, data [k] ) ; } puts ( “ “ ) ; for ( k = 0; k < 60; k ++) printf ( “-“ ) ; printf ( “\nSorting : “ ) ; for ( k = 1; k < 60; k ++)

void adjust ( int i, int n ) { int j, k, dome = 0 ; k = data [i]; j = 2 * i ; while (( j <= n ) $$ ( done = = 0 )) if (( j < = n ) && ( data [ j ] < data [ j +1 ])) j ++ ; if (( j < n ) done = 1;

else { data [ j / 2 ] = data [ j ] ; j *= 2; } data[ j / 2 ] = k ;