堆排序的基本思想：
对于 n 个元素的序列 {K1, K2, …, Kn}，当且仅当满足下列关系时称为堆，其中 2i 和 2i +１应不大于 n
其中，1 <= i <= n/2
当任意 K[i] 都小于 K[2i] 和 K[2i + 1] 时，为小根堆
当任意 K[i] 都大于 K[2i] 和 K[2i + 1] 时，为大根堆
堆排序是一种树形选择排序，可以将待排序数组看成是一个完全二叉树，则由堆的定义表明，该完全二叉树中，所有非叶子节点的值都不大于（或不小于）其左、右孩子节点的值。
因此，在一个堆中，堆顶元素（二叉树根节点）必定为该序列中的最大（或最小）元素。
所以堆排序就是，先构造堆，取堆顶元素，再构造新堆，重复这一过程，直到排序完成
假设待排序数组为：N = {55, 60, 40, 10, 80, 65, 15, 5, 75}; 结构如下：
构造大根堆，要使得该二叉树中所有非叶子节点的值都大于其左右节点，及使节点 1、2、3、4 的值都大于左右孩子节点。
初始化大根堆过程示意图：
/*
N 为待排序数组， target 为需要调整的非叶子节点
n 为节点个数
*/
void AdjustMaxHeap(int N[], int target, int n) {
int i = target;
int j = 2 * i + 1;
int temp = N[i];
while(j <= n) {
if(j < n && N[j] < N[j + 1]) { // 找出左右孩子的最大值
j++;
}
if(temp < N[j]) { // 不满足大根堆则交换元素值
N[i] = N[j];
i = j;
j = 2 * j + 1;
}
else {
break;
}
}
N[i] = temp;
}
构造小根堆，要使得该二叉树中所有非叶子节点的值都小于其左右节点，及使节点 1、2、3、4 的值都小于左右孩子节点。
void AdjustMinHeap(int N[], int target, int n) {
int i = target;
int j = 2 * i + 1;
int temp = N[i];
while(j <= n) {
if(j < n && N[j] > N[j + 1]) { // 找出左右孩子的最小值
j++;
}
if(temp > N[j]) { // 不满足小根堆则交换元素值
N[i] = N[j];
i = j;
j = 2 * j + 1;
}
else {
break;
}
}
N[i] = temp;
}
取堆顶元素，调整新堆过程示意图：
void HeapSort(int N[], int n) {
int i;
// 构造大根堆，元素从 0 开始
for(i = n/2 - 1; i >=0; i--) {
AdjustMaxHeap(N, i, n - 1);
}
int temp;
// 取堆顶元素，重新构造新堆
for(i = n - 1; i > 0; i--) {
temp = N[0];
N[0] = N[i];
N[i] = temp;
AdjustMaxHeap(N, 0, i - 1);
}
}
void test() {
int N[] = {55, 60, 40, 10, 80, 65, 15, 5, 75};
HeapSort(N, 9);
int i;
for(i = 0; i < len; i++) {
printf("%d ", N[i]);
}
printf("\n");
}
测试结果：
E:\C_demo>heapsort.exe
5 10 15 40 55 60 65 75 80