1964年，J.willioms和Robert W．Floyd提出了一种改进的树形选择排序——堆排序。只需要一个记录大小的辅助空间，每个待排序记录仅占一个单元的存储空间。
void heap_sort(const int n,int *a) /*n为待排序元素个数，a为待排序数组*/
{
int m = n - 1;
/*建初始堆*/
int i = n - 1;
while ((i - 1) / 2 >= 0)
{
if (a[i] > a[(i - 1) / 2])
{
int temp = a[(i - 1) / 2];
a[(i - 1) / 2] = a[i];
a[i] = temp;
}
--i;
}
/*开始排序*/
for (;m > 0;--m)
{
int chd = 1;
/*“输出”堆顶元素*/
int temp = a[m];
a[m] = a[0];
a[0] = temp;
/*调整堆*/
i = 0;
while (chd < m)
{
if ((chd + 1) < m && a[chd] < a[chd + 1])
chd = chd + 1;
if (a[chd] <= a[i])
break;
else
{
int swp = a[chd];
a[chd] = a[i];
a[i] = swp;
}
i = chd;
chd = 2 * i + 1;
}
}
}
1. 在需要两个元素互换值的时候，我刚开始写了如下的swap函数来实现，但是后来发现中枪了，经过测试之后，我才想起谭浩强版本的C语言教程里就讲过，实参到形参的传递方式是单向的“值传递”，在调用swap函数时，系统为形参分配内存空间，然后把实参的副本传给形参所占的空间；也就是说，执行函数之后，实参的值并未改变！！！在C++里，应该可以通过将形参声明为引用类型来直接操纵实参吧，C语言里面，则可通过指针来实现对实参的修改。但因为这个功能本身就很简单，封装成函数的确可以令代码看起来简洁、清晰，但是,函数调用的开销可能要抵消掉这个好处，所以——就直接展开为代码吧，也才三行简单语句而已。
void swap(int i,int j)
{
int temp = i;
i = j;
j = temp;
}
2. 在for循环里面，我先是把对变量i的赋值放在了for后面的小括号里，但没有明确自己实际上需要的是每一次循环都要对i赋一个初始值0，而for循环的执行只做一次初始化工作！于是，我又耗掉了大把时间来纠结自己的思路。。。。。。如果用while循环替代这一层，显得没有for那么华丽，却不会像for那么容易出错。
3. 内层while循环里。因为堆特性并没有描述兄弟结点之间的逻辑关系，所以重调堆的过程显得比建初始堆要麻烦，不但要注意边界的计算，还要处理兄弟结点的关系，更要留心循环不变式的保持，也就是说，怎样对迭代变量赋值来使迭代递进......直至迭代正确完成。
4. 另外，很多文献都讲到父结点和子结点之间的下标关系是a[i],a[2i]和a[2i
+ 1]......由于这里采用数组，而数组的起始下标是0，这里需要留心，像上面那样变动一下。
严蔚敏/吴伟民的《数据结构(C语言版)》(P282)里提到，堆排序方法对n较大的文件是很有效的，但对记录数较少的文件并不值得提倡，因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。此外，堆排序在最坏情况下的时间复杂度也为O(n log n),相对于快速排序来说，这是堆排序最大的优点。
《编程珠玑》里面专门用一个章节来探讨堆排序,里面把自下而上建堆和自顶向下调整堆都用函数模块来实现，最后出来的排序代码很简洁明了，但这是外表上的，实际也做着同样的事；不过，功能模块化是一个好的编程习惯嘛，我想。