1、什么是堆
首先它是一颗完全二叉树，并且父结点的值大于子节点的值(最大堆)或父结点的值小于子结点的值(最小堆)。
小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。
大根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。
2、堆排序
利用了大根堆或最小堆堆顶记录的关键字最大或最小这一特征，使得在当前无序区中选取最大或最小的关键字变得简单。
用大根堆排序的基本思想
① 先将初始文件R[0..n-1]建成一个大根堆，此堆为初始的无序区。（max_heapify()函数完成建立最大堆的功能）
② 再将关键字最大的记录R[0]（即堆顶）和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0..n-2]和有序区R[n-1]，且满足R[0..n-2].keys≤R[n-1].key
③由于交换后新的根R[0]可能违反堆性质，故应将当前无序区R[0..n-2]调整为堆。然后再次将R[0..n-2]中关键字最大的记录R[0]和该区间的最后一个记录R[n-2]交换，由此得到新的无序区R[0..n-3]和有序区R[n-2..n-1]，且仍满足关系R[0..n-3].keys≤R[n-2..n-1].keys，同样要将R[0..n-3]调整为堆。
……
直到无序区只有一个元素为止。(HeapSort()对最大根堆进行排序)
可得：若升序排列，应该建立最大堆，若降序排列，建立最小堆。
代码如下：
// Array是待调整的堆数组，i是待调整的数组元素的位置，即待调整的父结点，size是数组的长度,即结点总数
void heapify(int Array[],int i,int size)
{
if(i<size)
{
int left=2*i+1;
int right=2*i+2;
int largest=i;//假设最大的节点为父结点
//确定三个结点中的最大结点
if(left<size)
{
if(Array[largest]<Array[left])
largest=left;
}
if(right<size)
{
if(Array[largest]<Array[right])
largest=right;
}
//开始交换父结点和最大的子结点
if(largest!=i)
{
int temp=Array[largest];
Array[largest]=Array[i];
Array[i]=temp;
heapify(Array,largest,size);//对已经调整的结点做同样的交换
}
}
}
//注：上面函数的调用作了如下假设：待调整的i结点所有的子结点都满足堆的条件，故调用该函数应该
// 从最后一个结点开始调整为最大堆建堆过程，建立最大堆
void max_heapify(int Array[],int size)//调整最大堆，从最后一个结点开始调整
{
int i;
for(i=size-1;i>=0;i--)
heapify(Array,i,size);
}
// 堆排序算法，排序过程
void HeapSort(int Array[],int size)
{
int i;
for(i=size-1;i>=0;i--)
{
max_heapify(Array,i+1);//每次建立最大堆，将它的大小减1，砍断
//将根结点(最大结点)与最后一个结点交换
int temp=Array[0];
Array[0]=Array[i];
Array[i]=temp;
}
}
int main()
{
int a[]={10,23,8,2,52,35,7,1,12};
int length=sizeof(a)/sizeof(int);
printf("数组元素如下所示: \n");
for(int i=0;i<length;i++)
printf("%4d",a[i]);
printf("\n");
printf("创建好堆以后的数组元素如下所示: \n");
max_heapify(a,length);
for(i=0;i<length;i++)
printf("%4d",a[i]);
printf("\n");
HeapSort(a,length);
printf("经过排序后的堆,数组元素如下所示 : \n");
for(i=0;i<length;i++)
printf("%4d",a[i]);
printf("\n");
return 0;
}
注：堆排序的最坏时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1），
它是不稳定的排序方法。