利用堆(小顶堆)进行排序的过程，首先把待排序序列(R1,R2,…,Rn)转换成一个堆。这时，根结点具有最小值，输出根结点(可以将其与堆数组中的末尾元素交换，此时末尾元素就是最小值)，然后将剩下的n-1个结点重新调整为一个堆。反复进行下去，直到剩下一个结点为止。
所以实现堆排序主要需要解决两个问题：
1.如何将n个元素的序列建成堆。
2.输出堆顶元素后，怎样调整剩余n-1个元素，使其关键字成为一个新堆。
首先讨论问题2的调整方法：当输出一个堆顶元素后，将最后一个元素送入堆顶，此时堆被破坏。将根节点与左右孩子中较小的元素进行交换，如果与左孩子交换，则破坏的是左子树堆，如果与右孩子交换，则破坏的是右子树堆。继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。这个调整过程叫做筛选。
再来讨论问题1的建堆过程：对初始序列建堆的过程就是一个反复进行筛选的过程。若将n个结点序列看成一颗完全二叉树，则最后一个结点是第[n/2]个结点的孩子结点，对第[n/2]个结点为根的子树进行筛选，使之成为堆，直到根节点。如图所示的建堆过程：
空间复杂度：O(n)
时间复杂度：O(n lb n)
稳定性：不稳定
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
void Input(); //输入数组
void Output(); //输出数组
void sift(int k, int length); //将序列调成为堆
void creatHeap(int length); //建堆
void HeapSort(); //堆排序
int arr[MAXSIZE];
int count = 0;
//将序列调整为堆
/*
k 根结点所在的数组下标
length 待调整序列的长度
*/
void sift(int k, int length)
{
int i, j, t;
int finished = 0; //标志筛选是否完成,0表示未完成
t = arr[k]; //暂存根记录
i = k;
j = 2 * i; //左孩子结点
while (j <= length && !finished)
{
if (j < length && arr[j] > arr[j + 1]) //若存在右子树，且右子树根的关键字小，则沿右分支筛选
j = j + 1;
if (t <= arr[j])
finished = 1; //筛选完毕
else
{
arr[i] = arr[j];
i = j;
j = 2 * i;
} //继续筛选
}
arr[i] = t;
}
//建堆
void creatHeap(int length)
{
int i, n = length;
for (i = n / 2; i >= 1; i--)
sift(i, n);
}
//堆排序
void HeapSort()
{
int n, i, tmp;
creatHeap(count);
n = count;
for (i = n; i >= 2; --i)
{
//将堆顶记录和堆中最后一个记录交换
tmp = arr[1];
arr[1] = arr[i];
arr[i] = tmp;
sift(1, i - 1); //调整堆
}
}
//输入函数
void Input()
{
int x, i;
char s;
printf("please input less than 100 numbers, end with enter:\n");
for (i = 1; s != '\n'; i++)
{
scanf("%d", &arr[i]);
s = getchar();
count++;
}
}
//输出函数
void Output()
{
//每次调整堆后得出一个最小值，与最后一个元素交换
//所以这里逆序输出可以得到记录按从小到大排列的顺序
printf("sorted numbers:\n");
for (int i = count; i >= 1; --i)
{
printf("%d\t", arr[i]);
}
printf("\n");
}
int main()
{
Input();
HeapSort();
Output();
system("pause");
return 0;
}
运行结果：
