堆排序利用了大根堆的两个特点：
1. 堆顶元素是最大元素；
2. 后一次堆调整可以在前一次的基础上进行；
堆排序利用了数组的一个特点：
1. 快速定位指定索引的元素；
使用了以上的特点使得对无序数组进行排序变得简单而高效。
1. 先将初始文件R[0..n-1]建成一个大根堆，此堆为初始的无序区
2. 再将关键字最大的记录R[0]（即堆顶）和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0..n-2]和有序区R[n-1]，且满足R[0..n-2].keys≤R[n-1].key
3. 由于交换后新的根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[1..n-3].keys≤R[n-2..n-1].keys，同样要将R[0..n-3]调整为堆。
1. 建堆，建堆是不断调整堆的过程，从len/2-1处开始调整，一直到根结点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2-1到0处一直调用调整堆的过程，相当于o(h1)+o(h2)…+o(hlen/2)其中h表示结点的深度，len/2表示结点的个数，这是一个求和的过程，结果是线性的O(n)。
2. 调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较结点i和它的孩子结点left(i),right(i)，选出三者最大者，如果最大值不是结点i而是它的一个孩子结点，那边交互结点i和该结点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。
3. 堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根结点取出(一般是与最后一个结点进行交换)，将前面len-1个结点继续进行堆调整的过程，然后再将根结点取出，这样一直到所有结点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)。由于建堆只调用了一次，当n很大，即元素个数较多时，建堆过程的时间消耗可以忽略不计。如果n值比较小，则建堆过程的时间消耗不能忽略。
#include <stdio.h>
#define N 10
void heap_build(int array[], int length);
void heap_adjust(int array[], int i, intlength);
void heap_sort(int array[], int length);
int main(void)
{
intbuffer[N] = {1,2,3,4,5,6,7,8,9,0};
inti;
/*buildup heap*/
heap_build(buffer,N);
for(i= 0; i < N; i++)
{
printf("%3d",buffer[i]);
}
printf("\nbuildheap successfully!\n");
/*heapsort*/
heap_sort(buffer,N);
for(i= 0; i< N; i++)
{
printf("%3d",buffer[i]);
}
printf("\nheapsort successfully!\n");
}
void heap_build(int array[], int length)
{
inti;
/*调整第一个非叶子结点至根结点*/
for(i = length / 2 - 1; i >= 0; i--)
{
heap_adjust(array,i, length);
}
}
void heap_adjust(int array[], int i, intlength)
{
intlchild, rchild, max;
inttemp;
while(i< length -1)
{
lchild= 2*i + 1;
rchild= 2*i + 2;
max= i;
if(lchild < length)
{
if(array[max] < array[lchild])
{
max= lchild;
}
}
else /*该结点不存在叶子结点，即该结点本身就是叶子结点*/
{
break;
}
if(rchild < length)
{
if(array[max] < array[rchild])
{
max= rchild;
}
}
if(max != i) /*该结点小于其子结点*/
{
/*交换，使该结点下移一层*/
temp= array[i];
array[i]= array[max];
array[max]= temp;
/*继续调整子结点，直至满足大根堆条件*/
i= max;
}
else /*该结点满足大根堆条件，不需调整*/
{
break;
}
}
}
void heap_sort(int array[], int length)
{
inti;
inttemp;
for(i = length - 1; i > 0; i--)
{
/*交换根结点和最后一个结点*/
temp= array[i];
array[i]= array[0];
array[0]= temp;
/*在剩余无序区域中，继续调整根结点使之成为大根堆*/
heap_adjust(array,0, i);
}
}
原文：http://blog.csdn.net/u012914709/article/details/44498733