堆排序是对树形选择排序的改进，它首先将整个待排序列构建成一个堆，然后将堆顶元素与最后一个元素交换，由此得到一个有序元素和一个长度减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);
    }
}

堆排序的平均时间复杂度为O(n㏒ⁿ)，并且最差时间复杂度也为O(n㏒ⁿ)，而且它仅需要一个记录大小的额外存储空间。这就是说，无论输入什么，它都能保证以与n㏒ⁿ成比例的时间把n个元素排好序，没有什么最坏运行时间的输入使得排序运行明显变慢（不像快速排序），也无需巨大的额外辅助空间（不像归并排序）。这两个优点是堆排序有实用意义的两个主要原因。

此外，堆排序对于解决在n个元素中找出第k大元素（或前k个最大元素）也很有用，特别是在k比较小而n比较大的情况。在算法中，我们可以在把第k个元素从堆顶移出时停止其继续运行。

堆排序对于小文件排序时并不值得提倡，但对于较大的文件，堆排序还是很有效的。

竞争的排序算法

堆排序的主要竞争方法是快速排序和归并排序。堆排序和归并排序的选择主要归结于不稳定的排序和需要额外内存的排序之间的选择；堆排序和快速排序的选择归结于平均情况下速度和最坏情况下速度之间的选择。