堆排序的概念：
首先，我们先要理解堆的定义，
堆定义：n个关键字序列K1,K2,...,Kn称为（Heap），当且仅当该序列满足如下性质（简称：堆性质）：
（1）k(i)<=k(2i) 且 k(i)<=k(2i+i) (1<=i<=n/2),当然，这是最小根堆，
（2）k(i)>=k(2i) 且 k(i)>=k(2i+i) (1<=i<=n/2),大根堆则换成>=号。
k(i)相当于二叉树的非叶结点，k(2i)则是左孩子，k(2k+1)是右孩子
若将此序列所存储的向量R[1...n]看做是一棵完全二叉树的存储结构，则堆实际上是满足如下性质的完全二叉树：
树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
下面举例来具体说明什么是堆，
例：关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足性质1和性质2，故它们均是堆，其对应的完全二叉树分别如小根堆实例和大根堆示例所示。
那么堆排序则是利用了大根堆(或)小根堆堆顶记录的关键字最大(或最小)这一特征，使得在当前的无序区中选取
最大(或最小)关键字的记录变得简单。
我们想想看，如果是大根堆的话，那么它的最大根肯定是是里面的最大值，如果我们将其取走，
将剩下的数值在重新排列成堆，那么，它现在的顶根肯定又是最大值，
循环下去的话，我们会把一个个的最大值都给拆去出来，那么它们的排列顺序，肯定是由大到小的
这样，我们就完成了堆排序。
下面给出堆排序的C版代码：
void HeadSort(SqList *L){
int i;
for(i=L->length/2;i>0;i--){
HeapAdjust(L,i,L->length);
}
for(i=L->length;i>1;i--){
swap(L,1,i);
HeadAdjust(L,1,i-1);
}
}
void HeapAdjust(SqList *L,int s,int m){
int temp,j;
temp = L->r[s];
for(j=2*s;j<=m;j*=2){
if(j<m&&L->r[j]<L->r[j+1]){
++j;
}
if(temp>=L->r[j]){
break;
}
L->r[s] = L->r[j];
s=j;
}
L->r[s] = temp;
}
上面的代码中，首先我们要无序的数值进行一次堆排序，然后，将最大数值和末尾的数值交换，
并且让需要排序的数据长度减1，这样，剩下的数据再次进行排序，然后，每次结束后，都首末相调，长度减1，
最终我们得到的结果，肯定是由小到大的顺序表。
其中最令我们关注的应该是堆调整的算法了。
在HeapAdjust 方法中，我们传入了数组的引用，需要调整的非叶节点的最大值，和数组的最大长度。
其中s是非叶节点的最大值，它是根据数组的长度/2取整的来的。
我们想想看，如果是9个数值，那么如果按照堆排序的话，肯定是顶根节点是一个数值，下面两个子节点，
而节点又有节点，所以我们我们按从上之下的逻辑结构排，它们的个数肯定是1-2-4-2，
就如同上面的图片一样，那么需要调整的节点数肯定就是上面的非叶子节点了。一共有4个，也就是数组长度的1半了。
我们以顶根的下标为1，那么如果传入s的初始值应该就是非叶子节点的最大下表了。
首先，我们把该下标所对应的值保存为临时变量
然后取得这个节点的它的孩子节点，如果孩子节点的长度小于数组的最大长度，并且它的左孩子节点小于右孩子节点
则存储孩子节点的j下标+1，这里，我们的目的就是要获得孩子节点中的最大值的下标。
然后，用中间变量，也就是它们的父节点，与最大的孩子节点进行比较，
如果父节点大于孩子节点，则跳出循环，
但是如果小于呢?这是我们要将最大的孩子节点升级成为父节点，就是将孩子节点的值赋值给父节点。
并且将要s下标指向j，也就是最大孩子节点的初始位置，
这时j乘以2，j是当时最大的孩子，我们要继续找，是否，以它为父节点，它的孩子有比临时变量大的。
如果我们找到，则将孩子的值赋值给父节点r[s] = r[j] ,因为通过上次的循环，此时的s指向上次的最大孩子节点。
所以，再次赋值，就是将孩子的最大孩子节点赋值给父节点。
然后，在将j指向最大还是节点。
知道循环结束。
我们用中间变量替换最大孩子节点所在的值，至此，对堆的调整结束，它的根是目前最大的数值
后面的循环中，我们指明需要调整的其实位置是顶层位置，因为是收尾交换，其它数据的顺序就不要动了。
当循环结束之后，则完成了堆排序
下面给出java版的实现：
package com.fortune.test;
/**
* Created with IntelliJ IDEA.
* User: liupeng
* Date: 12-7-10
* Time: 下午5:27
*/
public class HeapSortTest {
public static int[] head = new int[]{50, 10, 90, 30, 70, 40, 80, 60, 20};
public static void main(String args[]) {
int temp;
int i;
for (i = head.length / 2 - 1; i >= 0; i--) {
HeapAdjust(i, head.length - 1);
}
for (i = head.length - 1; i > 0; i--) {
temp = head[0];
head[0] = head[i];
head[i] = temp;
HeapAdjust(0, i - 1);
}
for (int j = 0; j < head.length; j++) {
System.out.print(head[j] + " ");
}
}
public static void HeapAdjust(int start, int length) {
int temp, j;
temp = head[start];
for (j = 2 * start + 1; j <= length; j = j * 2 + 1) {
if ((j < length) && (head[j] < head[j + 1])) {
++j;
}
if (temp >= head[j]) {
break;
}
head[start] = head[j];
start = j;
}
head[start] = temp;
}
}
