堆排序是对树形选择排序的改进，它首先将整个待排序列构建成一个堆，然后将堆顶元素与最后一个元素交换，由此得到一个有序元素和一个长度减1的堆。由于交换后新的堆顶元素可能不满足堆的定义，因此需要将新的堆重新进行堆化（堆化无需重新建堆，只需做少许调整），在堆化完成之后再次将堆顶元素与堆的最后一个元素交换，由此再得到一个新的有序元素和一个长度减1的堆。然后再重新进行堆化，再交换。。。这样一直下去，直到整个堆只有一个元素为止。这样也就完成了对序列的排序。由这个排序的过程也可以知道，堆排序和简单选择排序不同，不是从前往后慢慢有序，而是从后往前慢慢有序。
堆排序的C/C++代码实现：
void heapify(int sort_array[], int k, int m)
{
int temp = sort_array[k];
for (int j = 2 * k; j <= m; j *= 2) {
if (j < m && sort_array[j] < sort_array[j+1]) ++j;
if (!(temp < sort_array[j])) break;
sort_array[k] = sort_array[j];
k = j;
}
sort_array[k] = temp;
}
void heap_sort(int sort_array[], int length)
{
int i, temp;
for (i = (length - 1) / 2; i >= 0; --i)
heapify(sort_array, i, length - 1);
for (i = length - 1; i > 0; --i) {
temp = sort_array[0];
sort_array[0] = sort_array[i];
sort_array[i] = temp;
heapify(sort_array, 0, i - 1);
}
}