对排序的实现思路有两种
第一种：1.构建最小堆。2.将最小堆的堆顶元素取出放到辅助数组的0号下标。3.重新调整成最小堆（向上调整） 4.重复2-3
第二种：1.构建最大堆。2.将堆顶元素（0号）与最后一个元素调换位置。3.最后一个元素不变，剩下的数据调整成最大堆。 4.重复2-3。
这里用的是第二种方式。
几点说明：
1.构建堆用的是数组来存储，即堆顶为s[0],第一层为s[1],s[2]以此类推。
2.下面的程序可能存在bug，因为是笔者用一组写在代码里面的数组来测试的。旨在说明问题。
3.为了方便，所有函数的参数都传进数组，直接在数组上做位置调整（对于数组来说，似乎也只能这么做）。
4.堆排序应该是 heap sort 英语没学好真是悲哀。
直接上代码：
//Sort.h 不好意思写成了头文件
#include<iostream>
using namespace std;
int Max(int s[],int a,int b)//取两数中较大的数的下标
{
return s[a]>s[b]?a:b;
}
/*
int Min(int s[],int a,int b)
{
return s[a]<s[b]?a:b;
}
*/
void swap(int s[],int a,int b)//交换两个数的位置
{
int temp;
temp = s[a];
s[a]=s[b];
s[b] = temp;
}
void FixDown(int s[],int a,int n)//向下调整算法
{
int temp = a;//这句没什么用，既然写在这里了就不删掉了。
int max = Max(s,temp*2+1,temp*2+2);//取最大值，在下面用到
if(s[temp]>=s[max]||(temp*2+2)>n||(temp*2+1)>n)//如果已经是局部（以s[temp]为根的）最大堆，或者s[temp]是叶子节点，直接返回
return;
if(s[temp]<s[max])//否则如果不是局部最大堆，调整。
{
swap(s,temp,max);//交换s[temp]和其叶子节点中较大的那个的数据。（如果不是最大那个的话调整完了还不是最大堆，而程序不会察觉）
FixDown(s,max,n);//递归
}
}
void Head(int s[],int n)//构造最大堆，只在一开始的时候用，其实也是调用向下调整算法
{
for(int i=(n-1)/2;i>=0;i--)//注意这里循环。向下调是从倒数第二层不断网上调整的。
{
FixDown(s,i,n-1);
}
}
void HeadSort(int s[],int n)//排序
{
Head(s,n);//=====注意：创建最大堆（把数组里面的元素重排）
int j=n-1;//数组尾部
while(j>0)
{
if(s[0]>s[j])//这句主要是最后一次的时候用。没有if也没关系
{
swap(s,0,j);//调换
FixDown(s,0,j-1);//向下调整。注意此时调整的最后一个元素是temp[j-1],不会访问到j，也就是说j被固定了。
}
j--;
}
}
void Sort(int s[],int low,int high)//sort函数，外部接口，可以忽视。因为里面其实就是一条语句，调用上面的函数
{
HeadSort(s,high);
}
void Show(int s[],int n)
{
for(int i=0;i<n;i++)
cout << s[i] << " ";
}
下面是测试文件
#include"Sort.h"
int main()
{
//int s[]={1,23,3,45,23,5,6,741,2,8,561,395,123,5110};
int s[] = {1,2,3,4,5,6,7,8,9,10};
int n = 10;
Sort(s,0,n);
cout << "排序后：";
Show(s,n);
return 0;
}
程序的运行过程是这样子的：
1.数组传进来，调用Sort函数。之所以写成这么函数，是因为以后写别的排序算法的时候，在里面调用就可以了，练练自己程序扩展的用法。
2.调用堆排序函数--》Headsort函数 《----算法从这里开始
3.先把数组调整成最大堆==》Head函数
4.现在拿到最大堆之后，s[0]跟s[j]换（j=n-1）。重新调整，循环。
完成。
补充：关于向下调整，如果上面讲的不清楚，可以找相应的博客来看，那种带图片分析的，一看就懂。
C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码
将C语言梳理一下，分布在以下10个章节中：
Linux-C成长之路（一）：Linux下C编程概要
Linux-C成长之路（十）：其他高级议题