堆
堆必须同时具备两个特性：1）结构性；2）堆序性
结构性：
堆是一棵完全二叉树，所谓完全二叉树即叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
堆序性：
堆序性说得通俗一点儿就是，父节点中的元素不小于（不大于）任意子节点的元素。
所以，在一个大根堆中，一个节点的元素在其子树所有元素组成的集合中必定是最大值。
堆的存储
一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+1和2*i+2。
节点下沉
“节点下沉”的目的是在此二叉树中将根节点的元素放至合适的坑位，相应地调整其他元素，最终使得包括根节点在内的整棵二叉树都满足“堆序性”。
“节点下沉”的实施方案说来也很简单：当父节点的元素值小于左子节点的元素值或者右子节点的元素值时，将父节点的元素值与左右子节点较大的元素值进行交换，针对交换后的父节点，循环执行“元素下沉”操作，“元素下沉”的终止条件就是父节点的元素值不小于其任意左右子节点的元素值，或者当前父节点无子节点（即当前节点为叶子节点）。
算法描述
- 将初始待排序关键字序列
(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； - 将堆顶元素
R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]； - 由于交换后新的堆顶
R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
#include <stdio.h>
#define LeftChild(i) (2*(i)+1)
void swap(int *a,int *b){
int c = *a;
*a = *b;
*b = c;
}
//下沉
void downSortArray(int num[], int index,int count){
int i = index;
int child;
for (;LeftChild(i)<count; i = child){
//取子节点中 较大节点
child = LeftChild(i);
if ((child +1)< count && num[child+1]>num[child]){
child++;
}
//如果需要则交换
if (num[i]<num[child]){
swap(&num[i],&num[child]);
}else{
break;
}
}
}
//堆排序
void heapSort(int num[], int count){
//构建大根堆
for (int i = count/2; i>=0; i--) {
downSortArray(num,i,count);
}
for (int i=0; i<count; i++) {
printf("%d ",num[i]);
}
printf("\n");
//并交换，下沉
for (int i = count-1; i>=0; i--) {
swap(&num[i],&num[0]);
downSortArray(num,0,i);
}
}
int main() {
//读取输入数据
int num[100] = {0};
int count;
scanf("%d",&count);
for (int i = 0; i<count; i++) {
scanf("%d",&num[i]);
}
//堆排序
heapSort(num,count);
//输出结果
for (int i=0; i<count; i++) {
printf("%d ",num[i]);
}
printf("\n");
}
复杂度分析
堆排序是一种选择排序，其时间复杂度为O(nlogn)
