堆排序是基于二叉树。n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：

(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于的非，K(2i）则是左子节点，k(2i+1）是右子节点。

堆排序的几个关键点：

1、一个节点的两个子节点已经是有序堆，调整这个节点为有序堆(递归调整)；

2、创建堆：调整第一个非叶节点为有序堆，逐级向上，直到整个数组为有序堆。

3、堆顶与最后一个叶子节点调换，堆变小，再调整堆，再调换，直到堆大小为1，排序完成。

附上代码：

#include "stdafx.h"#include 
     
      /* * L     初始无序堆 * n     节点序号 * size  无序堆节点个数 */void Heapify(int L[], int n, int size){    int rchild=2*n+1;    int lchild=2*n;    if (rchild<=size)    {        int max=L[lchild]>L[rchild] ? lchild : rchild;        if (L[n]
      
       0; i--) // 从最低层的节点开始创建有序堆，直到整个堆是有序堆。    {        Heapify(L,i,size);    }}// L[0]是暂存区void HeapSort(int L[], int size){    BuildHeap(L,size);    for (int i=size; i>0; i--)    {        L[0]=L[1];        L[1]=L[i];        L[i]=L[0];        Heapify(L,1,i-1);    }}int main(int argc, char* argv[]){    // 待排序数据不包括L[0]    int L[13]={
   5,1,7,2,90,6,-5,23,10,4,50,12,5};    int i=0;    for (i=1; i<13; i++)    {        printf("%5d",L[i]);    }    printf("\n");    HeapSort(L,12);    for (i=1; i<13; i++)    {        printf("%5d",L[i]);    }    printf("\n");    return 0;}