做yy头像的网站百度官网下载
堆（二叉树的应用）：
- 完全二叉树。
- 最大堆：每个节点比子树所有节点的数值都大，根节点是最大值。
- 父子索引号关系（根节点为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 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
