堆（二叉树的应用）：
- 完全二叉树。
- 最大堆：每个节点比子树所有节点的数值都大，根节点是最大值。
- 父子索引号关系（根节点为0）：（向上）子节点x，父节点(x-1) // 2。（向下）父节点x，左子节点2x+1，右子节点2x+2。
- 一般用数组实现堆。
堆排序：
第一步、构建堆（最大堆）。
- 找到最后的父节点：(最后元素的索引号-1) // 2。
- 从最后的父节点到根节点，依次向下调整（比较父节点和左右子节点，最大值为父节点）。
- 最终，根节点为最大值。尾指针指向最后节点。
第二步、排序
- 交换根节点和尾指针所在节点。此时，尾指针所在节点为目前正在排序中数据的最大值，保持不动。
- 尾指针向前（向左）移动一位。
- 从根节点到尾指针所在节点，依次向下调整。
- 此时，根节点为目前正在排序中数据的最大值（不包含已排序好且保持不动的最大值）。
第三步、重复第二步，直到尾指针指向根节点停止。
时间复杂度：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 one
if(left > end) break;
if(right <= end && array[left] < array[right]) maxchild = right;
else maxchild = left;
// parent compare with maxchild, if smaller than maxchild,change the position
if(array[start] < array[maxchild])
{
swap(&array[start], &array[maxchild]);
start = maxchild;
}
else break;
}
}
void heapsort(int *array, int length) // heap sort
{
// build a heap
int i = ceil((length - 1) / 2); // find the last parent
// from the last parent to 0 index, cycle ajust the heap down(parent compare 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 element
swap(&array[0], &array[n]);
// from 0 index, parent compare with left child and right child, max is parent
adjustdown(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
