采用数组存储二叉堆结构，数组下标从1开始，对于第i个结点，2i是其左孩子，2i+1是其右孩子。设结点总个数为n，若2i > n，则结点i没有左孩子；若2i+1 > n，则结点i没有右孩子。
堆排序最重要的是一步是筛选操作，即调用heapAdjust()函数。建立一个堆，是从最后一个非叶子结点(其下标为n / 2向下取整)开始，从下往上依次对每一个结点进行筛选。排序操作是当前堆的最大值(即堆顶元素，位于数组的第一个)与最后一个元素交换，再重新调整使之成为一个堆。然后对前n-1个元素重复执行上述操作。
#include <iostream>
#define MAX 10
using namespace std;
typedef struct {
int *elem;
int length;
} SqList;
//初始化顺序表
void init(SqList &L) {
L.elem = new int[MAX + 1];
L.length = 0;
for(int i = 1; i <= MAX; i++) {
cin>>L.elem[i];
L.length++;
}
}
//已知L.elem[s..m]中记录的关键字除L.elem[s]之外均满足堆的定义
//调整L.elem[s]的关键字，使得L.elem[s..m]成为一个大顶堆
void heapAdjust(SqList L, int s, int m) {
int j, temp;
temp = L.elem[s];
//沿关键字较大的孩子结点向下筛选
for(j = 2 * s; j <= m; j *= 2) {
//存在右子树且左子树的值小于右子树，j指向左右子树中较大的
if(j < m && L.elem[j] < L.elem[j + 1])
j++;
//已经是堆则退出
if(L.elem[j] <= temp) break;
L.elem[s] = L.elem[j];
s = j;
}
L.elem[s] = temp;
}
void heapSort(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.elem[1], L.elem[i]);
heapAdjust(L, 1, i - 1);
}
}
int main() {
SqList L;
init(L);
heapSort(L);
for(int i = 1; i <= L.length; i++)
cout<<L.elem[i]<<" ";
return 0;
}