其實堆排序就是對二叉樹的一種操作，使得二叉樹的左右孩子
節點都小於父節點。我使用的是數組的實現方式，
parent(i): return (i/2); //I的父節點下標，
left(i): return 2*i; //I的左子節點
right(i): return 2*i+1; //I的右子節點.
以上均為數組元素的標號位置，在存取元素時候，需要減一的。
舉一個例子：
共六個節點。在數組中存儲，每一個的編號如下：
|1 | 2 | 3 | 4 | 5 | 6 |
二叉樹的結構為
1
/ \
/ \
2 3
/ \ /
4 5 6
我使用的是遞歸的方法。
我首先從1節點開始遞歸。發現1節點的2、3子節點都有子節點，依次遞歸2，3。
2節點的子節點4、5沒有子節點，對2、4、5進行堆排序。然後返回。
3節點的子節點6沒有子節點，對3、6進行堆排序。然後返回。
1、2、3進行堆排序。首次堆排序完成。
1節點將是所有結果中的最值（最大或最小值）
然後將排序的數據減一，數組開始指針向後移動一位，返回第一步。直到排序數據為零。
（其實也可一將第一個數據，與最後一個數據交換，將要排序的數據減一，返回第一步也行的。）
下面是我寫的代碼，我在ubuntu中測試通過。與書中的方案不同，可能非最優方案，請大家諒解。一下是代碼。
[cpp]
/*
*main function:maximum heap sort
*Author:Reage
*Blog: http://blog.csdn.net/rentiansheng
*/
#include <stdio.h>
#include <stdlib.h>
/*swap *p1 and p2 value
*/
void swap(int *p1, int * p2){
*p1 += *p2;
*p2 = *p1 - *p2;
*p1 -= *p2;
}
/*Left child node subscript.
*得到第i個節點的左孩子節點在數組中的下標
*注意節點從1開始計算
*/
int left(int i){
return (2 * i -1);
}
/*Right child node subscript
*得到第i個節點的右孩子節點在數組中的下標
*注意節點從1開始計算
*/
int right(int i){
return (2 * i);
}
/*Maximum heap sort
*最大堆的排序方法
*@parameter
* p:要進行排序的數組的其實坐標
* location:當前要進行最大堆運算的父節點是樹中的第幾個節點，從1開始算起
* count:（樹）堆中的節點個數。
*/
void max_heap(int *p, int location, int count){
int l, r;
l = left(location);
r = right(location);
if(1 == count)return;
//當堆中第location的左孩子節點還有孩子節點。
//對location的左孩子節點遞歸最大堆的排序
if( 2 * (l + 1) <= count)
max_heap(p, l + 1, count);
//理由同上
if( 2 * (r + 1) <= count)
max_heap(p, r + 1, count);
//判斷location的右孩子節點是否存，
if(r + 1 > count){
//當location的右孩子節點不存，只要對location和左孩子進行最大堆排序
if(p[l] > p[location - 1]){
swap(p + l, p + location - 1);
}
}
else {
//將location與左右孩子節點做最大堆排序
if(p[l] > p[r]){
if(p[l] > p[location - 1]){
swap(p + l, p + location - 1);
}
}
else{
if(p[r] > p[location - 1]){
swap(p + r, p + location - 1);
}
}
}
}
int main(){
int count;
int i;
int *ptr;
printf("input count:");
scanf("%d", &count);
ptr = (int *) malloc(count * sizeof(int));
memset(ptr, 0, count);
for(i = 0; i < count; i++)
scanf("%d", ptr+i);
printf("\n");
for(i = 0; i < count; i++){
max_heap(ptr + i, 1, count - i);
printf("%d ", ptr[i]);
}
printf("\n");
return 0;
}
/*
*main function:maximum heap sort
*Author:Reage
*Blog: http://blog.csdn.net/rentiansheng
*/
#include <stdio.h>
#include <stdlib.h>
/*swap *p1 and p2 value
*/
void swap(int *p1, int * p2){
*p1 += *p2;
*p2 = *p1 - *p2;
*p1 -= *p2;
}
/*Left child node subscript.
*得到第i個節點的左孩子節點在數組中的下標
*注意節點從1開始計算
*/
int left(int i){
return (2 * i -1);
}
/*Right child node subscript
*得到第i個節點的右孩子節點在數組中的下標
*注意節點從1開始計算
*/
int right(int i){
return (2 * i);
}
/*Maximum heap sort
*最大堆的排序方法
*@parameter
* p:要進行排序的數組的其實坐標
* location:當前要進行最大堆運算的父節點是樹中的第幾個節點，從1開始算起
* count:（樹）堆中的節點個數。
*/
void max_heap(int *p, int location, int count){
int l, r;
l = left(location);
r = right(location);
if(1 == count)return;
//當堆中第location的左孩子節點還有孩子節點。
//對location的左孩子節點遞歸最大堆的排序
if( 2 * (l + 1) <= count)
max_heap(p, l + 1, count);
//理由同上
if( 2 * (r + 1) <= count)
max_heap(p, r + 1, count);
//判斷location的右孩子節點是否存，
if(r + 1 > count){
//當location的右孩子節點不存，只要對location和左孩子進行最大堆排序
if(p[l] > p[location - 1]){
swap(p + l, p + location - 1);
}
}
else {
//將location與左右孩子節點做最大堆排序
if(p[l] > p[r]){
if(p[l] > p[location - 1]){
swap(p + l, p + location - 1);
}
}
else{
if(p[r] > p[location - 1]){
swap(p + r, p + location - 1);
}
}
}
}
int main(){
int count;
int i;
int *ptr;
printf("input count:");
scanf("%d", &count);
ptr = (int *) malloc(count * sizeof(int));
memset(ptr, 0, count);
for(i = 0; i < count; i++)
scanf("%d", ptr+i);
printf("\n");
for(i = 0; i < count; i++){
max_heap(ptr + i, 1, count - i);
printf("%d ", ptr[i]);
}
printf("\n");
return 0;
}
