算法原理

堆排序定義：

n個序列 Al， A2，…， An 稱為堆，有下面兩種不同類型的堆。

• 小根堆：所有子結點都大於其父節點，即 Ai ≤ A2i 且 Ai ≤ A2i+ 1。
• 大根堆： 所有子結點都小於其父節點，即 Ai ≥ A2i 且 Ai ≥ A2i+ 1。

（數組是從0開始計算的，為了平衡考慮，使用 A2i + 1 和 A2i + 2）

若將此序列所存儲的向量 A[ 1... n] 看為一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於（或不小於）其左、右的節點（若存在）的關鍵字。

因此堆排序（HeapSort） 是樹形選擇排序。在排序過程中，將 R[l... n] 看成一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關係，在當前無序區中選擇關鍵字最大（或 最小）的 記錄。

用大根堆排序的基本思想：

（1） 先將初始 A[1... n] 建成一個大根堆，此堆為初始的無序 區。

（2） 再將關鍵字最大的記錄 A[1]（堆頂）和無序區的最後一個記錄 A[n] 交換，由此得到新的無序區A[1... n-1] 和有序區 A[n]，且滿足 A[1... n- 1] ≤ A[n]。

（3） 由於交換後新的根A[1]可能違反堆性質，故應將當前無序區 A[1... n- 1] 調整為堆。然後再次將 A[1... n-1] 中 關鍵字最大的記錄 A[1] 和該區間的最後一個記錄 A[n- 1] 交換，由此得到新的無序區 A[1... n- 2] 和有序區 A[ n-1... n]，且仍滿足關係 A[ 1... n-2] ≤ A[n- 1... n]，同樣要將 A[1... n- 2] 調整為 堆。

（4） 對調整的堆重複進行上面的交換，直到無序區只有一個元素為止。

構造初始堆必須用到調整堆的操作，現在說明 Heapify 函數思想方法。

每趟排序開始前，A[l… i] 是以 A[1] 為根的堆，在 A[1] 與 A[i] 交換 後，新的無序區 A[1… i-1]中只有A[1] 的值發生了變化，故除 A[1] 可能違反堆性質外，其餘任何結點為根 的子樹均是堆。因此，當被調整區間是 A[ low… high] 時，只須調整以 A[low] 為根的樹即可。

可以使用“ 篩選法” 進行堆的調整。 A[low] 的 左、 右 子樹（若 存在）均已是堆，這兩棵子樹的根 A[ 2low] 和 A[ 2low+ 1] 分別是各自子樹中關鍵字最大的節點。 若 A[low] 不小於這兩個孩子節點的關鍵字，則A[low]未違反堆性質，以 A[low] 為根的樹已是堆，無須調整；否則必須將 A[low] 和它的兩個孩子節點中關鍵字較大者進行交換，即 A[low] 與 A[large] （A[large]= max( A[2low]，A[2low+ 1])）交換。交換後又可能使節點 A[large] 違反堆性質。同樣，由於該節點的兩棵子樹（若存在）仍然是堆，故可重複上述調整過程，對以 A[large] 為根的樹進行調整。此過程直至當前被調整的節點已滿足堆性質，或者該節點已是葉子為止。上述過程就像過篩子一樣，把較小的關鍵字逐層篩下去，而將較大的關鍵字逐層選上來。

算法草稿

堆排序算法草稿

代碼實現

<code>#include <stdio.h>#include <stdlib.h>#define SUCCESS0#define PARAM_ERR-1int BuildMaxHeap(int * array, int low, int high){if(NULL == array){printf("%s para error", __func__);return PARAM_ERR;}//printf("Enter BuildMaxHeap low = %d, high = %d\\n", low, high);int left = 0, right = 0; /*子樹的索引*/int max = low; /*最大子節點的索引，默認[low]是堆的根 */int temp = 0;/*  * low 是根堆，默認[low] 是最大的點做在的位置 * 不用 2 * low 和 2 * low + 1, 是因為對於0為根的對來說，子樹就都在右邊了，樹就不平生了 * left = 2 * low; * right = 2 * low + 1;  * 當然，這麼用也沒什麼錯誤，就是樹不太平衡，像個瘸子 ;-D */left = 2 * low + 1;right = 2 * low + 2;/* * 有左子節點 且 [low] 不是最大節點，max取得左子樹 * 注意比較前，需要保證左子節點存在：left <= high */if((left <= high) && (array[left] > array[low])){max = left;} else {max = low;}/* * 有右子節點 且 [low] 不是最大節點，max取得左子樹 * 注意比較前，需要保證左子節點存在：right <= high */if((right <= high) && (array[right] > array[max])){max = right;}if(max != low){temp = array[max];array[max] = array[low];array[low] = temp;/* 對交換的子樹進行重新建堆*/BuildMaxHeap(array, max, high);}//printf("Left BuildMaxHeap low = %d, high = %d\\n", low, high);return SUCCESS;}int initMaxHeap(int * array, int size){if(NULL == array){printf("%s para error", __func__);return PARAM_ERR;}//printf("Enter initMaxHeap\\n");int i = 0;#ifdef DEBUGint k = 0;#endif/* * 只是到 size /2 而不是 size，因為後半部分通過 2*i +1  和  2 * i + 2 子樹方式完成了遞歸的構建 * 前半部分在初始化的時候，要逐個建堆 * for(i = size - 1; i >= 0; i--) 整個建堆也沒有錯，就是效率會差一些，隨著數組越大，效率越差 * 注意要包含 0 和 size / 2 ， 是個閉區間，不然少一個初次的建堆 * 還有一點非常重要，需要從後向前初始化，相當於需要先初始化好子樹，再初始化父一級的樹，這樣才可以 * 反過來的初始化順序是錯誤的，父一級錯誤，再初始化子一級也錯誤，二者就更加錯誤了     */for(i = size / 2; i >= 0; i--){BuildMaxHeap(array, i, size - 1);}#ifdef DEBUGprintf("%s: size = %d\\n", __func__, size);printf("init Heap [");for(k =0; k < size; k++){printf("  %d  ", array[k]);}printf("]  \\n");printf("\\n");#endif//printf("Left initMaxHeap\\n");return SUCCESS;}int HeapSort(int * array, int size){if(NULL == array){printf("%s para error", __func__);return PARAM_ERR;}int i = 0, j = 0;int temp = 0;#ifdef DEBUGint k = 0;#endif//printf("Enter HeapSort\\n");/*初始化構建大根堆*/initMaxHeap(array, size);/* 每輪提取構建有序區，然後對新的無序區的堆再次平衡 */for(i = size - 1 ; i > 0; i--){ /* 無序區逐步往前縮減，最後一個直接認為在有序區 *//* 交換 [0] 和 [i], i 進入有序區*/temp = array[0];array[0] = array[i];array[i] = temp;#ifdef DEBUGprintf("heapsize = %d, [max] = %d, 已經swap([0], [%d]) \\n", i + 1, temp, i);printf("[");/*有序區域*/for(k =0; k <= i; k++){printf("  %d  ", array[k]);}printf("]  , ");/*無序區域*/printf(" [");for(k = i + 1; k < size; k++){printf("  %d  ", array[k]);}printf("]\\n");printf("\\n");#endif/* 構建堆 [0, i-1] */BuildMaxHeap(array, 0, i - 1);}//printf("Left HeapSort");return SUCCESS;}int main(int argc, char ** argv){int array[10] = {7,3,5,8,0,9,1,2,4,6};int i = 0;printf("Before sort: \\n");for(i = 0; i < 10; i++){printf("  %d  ", array[i]);}printf("\\n");HeapSort(array, 10);printf("after sort: \\n");for(i = 0; i < 10; i++){printf("  %d  ", array[i]);}printf("\\n");return 0;}/<stdlib.h>/<stdio.h>/<code> 

調試編譯

gcc HeapSort.c -DDEBUG

調試輸出

<code>Before sort:  7    3    5    8    0    9    1    2    4    6initMaxHeap: size = 10init Heap [  9    8    7    4    6    5    1    2    3    0  ] heapsize = 10, [max] = 9, 已經swap([0], [9])[  0    8    7    4    6    5    1    2    3    9  ]  ,  [] heapsize = 9, [max] = 8, 已經swap([0], [8])[  3    6    7    4    0    5    1    2    8  ]  ,  [  9  ] heapsize = 8, [max] = 7, 已經swap([0], [7])[  2    6    5    4    0    3    1    7  ]  ,  [  8    9  ] heapsize = 7, [max] = 6, 已經swap([0], [6])[  1    4    5    2    0    3    6  ]  ,  [  7    8    9  ] heapsize = 6, [max] = 5, 已經swap([0], [5])[  1    4    3    2    0    5  ]  ,  [  6    7    8    9  ] heapsize = 5, [max] = 4, 已經swap([0], [4])[  0    2    3    1    4  ]  ,  [  5    6    7    8    9  ] heapsize = 4, [max] = 3, 已經swap([0], [3])[  1    2    0    3  ]  ,  [  4    5    6    7    8    9  ] heapsize = 3, [max] = 2, 已經swap([0], [2])[  0    1    2  ]  ,  [  3    4    5    6    7    8    9  ] heapsize = 2, [max] = 1, 已經swap([0], [1])[  0    1  ]  ,  [  2    3    4    5    6    7    8    9  ] after sort:  0    1    2    3    4    5    6    7    8    9/<code>

閱讀更多 六六哥講技術 的文章

關鍵字: 人工智能 小根堆 算法