堆排序利用了优先级队列——二叉堆——的有序性。

1.堆排序算法

用优先级队列排序N个元素的过程有两个步骤：

（1）将每个元素enQueue到一个二叉堆，构建一个优先级队列。

（2）将优先级队列执行N次deQueue操作，将这些元素按出队顺序进行排列即可。

2.堆排序时间复杂度

优先级队列的deQueue时间复杂度为O(logN)。

优先级队列的enQueue时间复杂度也是O(logN)。

对于N个元素的enQueue和deQueue，时间复杂度为O(NlogN)。

相对直接选择排序来说，时间复杂度上有一定的优化。

3.堆排序代码实现

代码如下所示：

    public void heapSort(T[] a, int size) {
        int i;
        T tmp;

        // 入堆
        for (i = size / 2 - 1; i >= 0; i--) {
            percolateDown(a, i, size);
        }

        // 出堆
        for (i = size - 1; i >= 0; --i) {
            tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;

            percolateDown(a, 0, i);
        }
    }

    public void percolateDown(T[] a, int hole, int size) {
        int child;
        T tmp = a[hole];
        while (hole * 2 + 1 < size) {
            child = hole * 2 + 1;
            if (child != size - 1 && a[child + 1] > a[child]) {
                child++;
            }
            if (a[child] > tmp) {
                a[hole] = a[child];
            } else {
                break;
            }
            hole = child;
        }
        a[hole] = tmp;
    }

4.堆排序适合场景

堆排序适合待排元素较多的场景。能保证最坏情况下时间复杂度为O(NlogN)。空间复杂度为O(1)

但是，堆排序为不稳定的排序。