堆（二叉樹的應用）：

• 完全二叉樹。
• 最大堆：每個節點比子樹所有節點的數值都大，根節點是最大值。
• 父子索引號關系（根節點為0）：（向上）子節點x，父節點(x-1) // 2。（向下）父節點x，左子節點2x+1，右子節點2x+2。
• 一般用數組實現堆。

堆排序：

第一步、構建堆（最大堆）。

1. 找到最后的父節點：(最后元素的索引號-1) // 2。
2. 從最后的父節點到根節點，依次向下調整（比較父節點和左右子節點，最大值為父節點）。
3. 最終，根節點為最大值。尾指針指向最后節點。

第二步、排序

1. 交換根節點和尾指針所在節點。此時，尾指針所在節點為目前正在排序中數據的最大值，保持不動。
2. 尾指針向前（向左）移動一位。
3. 從根節點到尾指針所在節點，依次向下調整。
4. 此時，根節點為目前正在排序中數據的最大值（不包含已排序好且保持不動的最大值）。

第三步、重復第二步，直到尾指針指向根節點停止。

時間復雜度：O(nlogn)

• 初次構建堆，時間約n。
• 每次向下調整，都是使用2x+1、2x+2，遍歷次數是logn（對數），幾乎每個元素都要重排，因此時間約 nlogn。
• 相對于nlogn而言，n可忽略，即總時間O(nlogn)。

空間復雜度：O(1)

• 在原位置排序，只重復使用了用于交換的臨時空間，不隨數據量的變動而變動，空間使用為常量(1)。

---

C語言實現思路：

先構建堆（最大堆），再排序。

void heapsort(int *array, int length)		// heap sort
{// 構建堆（最大堆）// 找到最后的父節點int i = ceil((length - 1) / 2);	// 從最后的父節點到根節點，依次向下調整（父子節點比較大小，最大值為父節點）for(; i >= 0; i--){adjustdown(array, i, length - 1);}// 排序// 交換根節點和尾指針所在節點，尾指針前移一位，從根節點開始向下調整for(int n = length - 1; n > 0; n--){swap(&array[0], &array[n]);adjustdown(array, 0, n - 1);}
}

因多次向下調整，多次交換兩個數據，因此，向下調整、交換數據分別用函數單獨實現。

交換兩個數據：

傳入的參數為數據的內存地址，將直接在內存地址進行數據交換。

void swap(int *a, int *b)
{int tmp = *a;*a = *b;*b = tmp;
}

向下調整：

向下在左右子節點中找到較大值的節點，父節點再與較大值的子節點比較大小，若子節點數值更大，父子節點交換位置。?

void adjustdown(int *array, int start, int end)		// adjust the heap down
{while(start < end){int left = 2 * start + 1, right = 2 * start + 2, maxchild;// 比較左右子節點，找到較大值的子節點if(left > end) break;if(right <= end && array[left] < array[right]) maxchild = right;else maxchild = left;// 與較大值的子節點比較，若子節點數值更大，交換父子節點的位置if(array[start] < array[maxchild]){swap(&array[start], &array[maxchild]);start = maxchild;}else break;}
}

---

完整代碼：（heapsort.c）

#include <stdio.h>
#include <math.h>/* function prototype */
void heapsort(int *, int);	// heap sort
void traverse(int *, int);	// show element one by one/* main function */
int main(void)
{int arr[] = {4,2,6,9,5,1,3};int n = sizeof(arr) / sizeof(int);traverse(arr, n);heapsort(arr, n);	printf("[ after heap sort ] ");traverse(arr, n);return 0;
}/* subfunction */
void swap(int *a, int *b)		// change the value of two datas
{int tmp = *a;*a = *b;*b = tmp;
}void adjustdown(int *array, int start, int end)		// adjust the heap down
{while(start < end){int left = 2 * start + 1, right = 2 * start + 2, maxchild;// left child or right child, find the max oneif(left > end) break;if(right <= end && array[left] < array[right]) maxchild = right;else maxchild = left;// parent compair with maxchild, if smaller than maxchild,change the positionif(array[start] < array[maxchild]){swap(&array[start], &array[maxchild]);start = maxchild;}else break;}
}void heapsort(int *array, int length)		// heap sort
{// build a heapint i = ceil((length - 1) / 2);			// find the last parent// from the last parent to 0 index, cycle ajust the heap down(parent compair with child)for(; i >= 0; i--){adjustdown(array, i, length - 1);}// sort (root is max, change max to the last, end pointer move a step to the left)for(int n = length - 1; n > 0; n--){// swap the first and last elementswap(&array[0], &array[n]);// from 0 index, compair with left child and right child, max is parentadjustdown(array, 0, n - 1);}
}void traverse(int *array, int length)		// show element one by one
{printf("elements(%d): ", length);for(int k = 0; k < length; k++){printf("%d  ", array[k]);}printf("\n");
}

編譯鏈接： gcc -o heapsort heapsort.c

執行可執行文件：?./heapsort

?