堆排序结合了插入排序和归并排序的优点，虽然不优于快速排序，但是有其独特的应用。
堆的基本结构是树，又称为二叉堆，分为最大堆和最小堆，两者都可以实现排序，此篇以最大堆为例介绍。
最大堆就是任意父节点的值不小于其子节点的值。
这就是一个最大堆：
首先，父节点与子节点的编号存在一定关系，可以通过三个函数互相推算：
int parent(int child) { return child/2; } int left(int parent) { return 2*parent; } int right(int parent) { return 2*parent+1; } 而维护最大堆性质的关键函数就是max，它的输入包含数组和一个下标pos，在调用max时假定以left（pos）和right（pos）为根节点的二叉堆都是最大堆，但是temp[pos]可能小于其孩子结点，那么要首先检查temp[pos]是否大于或等于两个孩子结点的值，如果均大于或等于，即完成，如果其中有比temp[pos]大的，取最大的与根节点的值交换，交换后以交换的结点为根节点的二叉堆可能不再符合最大堆，那么就要再次调用max，继续检查和更改，直到满足。 void max(int *temp, int pos, int size){ int l = left(pos); int r = right(pos); int largest; if (temp[l] > temp[pos] && l <= size) largest = l; else largest = pos; if (temp[r] > temp[largest] && r <= size) largest = r; if (largest != pos) { int k = temp[pos]; temp[pos] = temp[largest]; temp[largest] = k; max(temp, largest, size); } } 而如果要使得一个二叉堆成为最大堆，则需要从最底最右的非叶子结点开始调用max，这样才能保证每次调用max是，以pos的两个孩子结点为根节点的二叉堆为最大堆。易知最底最右的非叶子结点的下标就是size/2，所以可以写出build函数。void build(int *temp, int size) { for (int i = size/2; i > 0; i--) max(temp, i, size); } 举个例子：
对于图1的二叉堆，调用了build(temp,10)，那么则从5号结点为根节点开始调用max，结果为图2，图3是对4号结点调用的结果，图4是对3号结点调用的结果，然后对于2号结点调用max，左子节点16比根节点14大，从而交换，交换后的14大于其左右结点，所以max函数结束，结果是图5，接下来是对1号结点调用max了，子节点10和16都大于2，16又大于10，所以16和2交换，如图6，然后开始2作为根节点与7和14比较，结果是14与2交换，结果如图7，然后2又与8交换，如图8，至此，此二叉堆已经是最大堆了。
那么已经构造了最大堆，下面就开始实现排序了。
最大堆的一个特点就是1号结点，也就是根节点，值最大，所以我们可以将其取出，再将最大号的结点位置的值放在1号结点处，此时以1号结点两个子节点为根节点的仍是最大堆，所以一个max（temp，1，size）可以使二叉堆再次成为最大堆，只是这次的size是原size-1，循环上述过程直至堆中仅剩1个结点，排列结束。
void heapsort(int* temp, int size) { build(temp, size); int w = size; for(int i = 1; i < size; i++) { int k = temp[1]; temp[1] = temp[w]; temp[w] = k; w--; max(temp, 1, w); } } 下面是一个测试样例： #include<iostream> using namespace std; int parent(int child) { return child/2; } int left(int parent) { return 2*parent; } int right(int parent) { return 2*parent+1; } void max(int *temp, int pos, int size){ int l = left(pos); int r = right(pos); int largest; if (temp[l] > temp[pos] && l <= size) largest = l; else largest = pos; if (temp[r] > temp[largest] && r <= size) largest = r; if (largest != pos) { int k = temp[pos]; temp[pos] = temp[largest]; temp[largest] = k; max(temp, largest, size); } } void build(int *temp, int size) { for (int i = size/2; i > 0; i--) max(temp, i, size); } void heapsort(int* temp, int size) { build(temp, size); int w = size; for(int i = 1; i < size; i++) { int k = temp[1]; temp[1] = temp[w]; temp[w] = k; w--; max(temp, 1, w); } } int main() { int a[10]; a[0] = 100; a[1] = 10; a[2] = 4; a[3] = 7; a[4] = 12; a[5] = 20; a[6] = 1; a[7] = 0; a[8] = 14; a[9] = 7; heapsort(a, 9); cout << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << " " << a[5] << " " << a[6] << " " << a[7] << " " << a[8] << " " << a[9]; } 输出结果：
