先看看对堆的理解：

堆像一棵倒过来的树

• 堆就不同了，堆是一种经过排序的树形数据结构，每个结点都有一个值。
• 通常我们所说的堆的数据结构，是指二叉堆。
• 堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。

由于堆的这个特性，常用来实现优先队列，堆的存取是随意，这就如同我们在图书馆的书架上取书，虽然书的摆放是有顺序的，但是我们想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，我们可以直接取出我们想要的书。

接下来就是堆实现和堆排序了

这是贴出最大堆的构建，以及对最大堆的排序代码，复制到linux下可以直接编译运行：

#include <stdio.h>
//array是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度
//本函数功能是：根据数组array构建大根堆
void HeapAdjust(int array[],int i,int nLength)
{
        int nChild,c;
        int nTemp;
        for(;2*i+1<nLength;i=nChild)
        {
                //子结点的位置=2*（父结点位置）+1
                nChild=2*i+1;
                //得到子结点中较大的结点
                if(nChild<nLength-1&&array[nChild+1]>array[nChild])++nChild;
                //如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
                if(array[i]<array[nChild])
                {
                        nTemp=array[i];
                        array[i]=array[nChild];
                        array[nChild]=nTemp; 
                }
                else break; //否则退出循环
        }
}
//堆排序算法
void HeapSort(int array[],int length)
{
        int i,c;
        //调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
        //length/2-1是最后一个非叶节点，此处"/"为整除
        for(i=length/2-1;i>=0;--i)
        {
                HeapAdjust(array,i,length);
        }
        //从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
        for(i=length-1;i>0;--i)
        {
                //把第一个元素和当前的最后一个元素交换，
                //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
                array[i]=array[0]^array[i];
                array[0]=array[0]^array[i];
                array[i]=array[0]^array[i];
                //不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
                HeapAdjust(array,0,i);
        }
}
int main()
{
        int i;
        int num[]={0,8,2,3,5,4,9,7,1,6};
        HeapSort(num,sizeof(num)/sizeof(int));
        for(i=0;i<sizeof(num)/sizeof(int);i++)
                printf("%d ",num[i]);
        printf("\nok\n");
        return 0;
}

编译运行结果：

 gcc heap.c && ./a.out 

0 1 2 3 4 5 6 7 8 9 
ok