二叉堆结构的运用：堆排序

前文 二叉堆基础 介绍过二叉堆结构，二叉堆实现优先级队列 利用二叉堆结构实现了一个 SimpleMinPQ 优先级队列，插入队列的元素会按照从小到大的顺序取出。

本文将介绍堆排序算法，它是基于二叉堆性质衍生出来的一种全新排序算法，非常优雅和高效。

首先，我要复述一下二叉堆实现优先级队列的几个关键原理，如果你有任何不理解的地方，务必回去复习前文，否则无法理解堆排序。

1、二叉堆（优先级队列）底层是用数组实现的，但是逻辑上是一棵完全二叉树，主要依靠 swim, sink 方法来维护堆的性质。

2、优先级队列可以分为小顶堆和大顶堆，小顶堆会将整个堆中最小的元素维护在堆顶，大顶堆会将整个堆中最大的元素维护在堆顶。

3、优先级队列插入元素时，首先把元素追加到二叉堆底部，然后调用 swim 方法把该元素上浮到合适的位置，时间复杂度是 $O(\log N)$。

4、优先级队列删除堆顶元素时，首先把堆底的最后一个元素交换到堆顶作为新的堆顶元素，然后调用 sink 方法把这个新的堆顶元素下沉到合适的位置，时间复杂度是 $O(\log N)$。

那么最简单的堆排序算法思路就是直接利用优先级队列，把所有元素塞到优先级队列里面，然后再取出来，不就完成排序了吗？

// 直接利用优先级队列对数组从小到大排序
void sort(int[] nums) {
    // 创建一个从小到大排序元素的小顶堆
    SimpleMinPQ pq = new SimpleMinPQ(nums.length);
    // 先把所有元素插入到优先级队列中
    for (int num : nums) {
        // push 操作会自动构建二叉堆，时间复杂度为 O(logN)
        pq.push(num);
    }
    // 再把所有元素取出来，就是从小到大排序的结果
    for (int i = 0; i < nums.length; i++) {
        // pop 操作从堆顶弹出二叉堆堆中最小的元素，时间复杂度为 O(logN)
        nums[i] = pq.pop();
    }
}

因为优先级队列的 push, pop 方法的复杂度都是 $O(\log N)$，所以整个排序的时间复杂度是 $O(N \log N)$，其中 N 是输入数组的长度。

这个思路可以得到正确的排序结果，但空间复杂度是 $O(N)$，因为我们创建的这个优先级队列是一个额外的数据结构，它的底层使用了一个数组来存储元素。

所以，堆排序要解决的问题是，不要使用额外的辅助空间，直接在原数组上进行 sink, swim 操作，在 $O(N \log N)$ 的时间内完成排序。

你不妨自己思考几分钟，对比一下优先级队列增删元素的过程，其实利用 swim, sink 方法原地实现这两步并不难，应该可以独立思考出来。

在具体讲解堆排序代码实现之前，我先把二叉堆的 swim, sink 方法和配套的工具函数写出来，因为后文我会带你逐步优化堆排序的代码，就不重复实现这些函数了。

这些函数就是从 二叉堆实现优先级队列 中的优先级队列实现里抠出来的，把数组作为函数参数传入，其他的逻辑完全一样：