堆排序

堆排序是由美国计算机科学家J·W·J·威廉斯（J. W. J. Williams）在 1964 年发明的。在威廉斯的论文《Algorithm 232: Heapsort》中，他首次介绍了堆排序算法。堆排序，即是使用堆这种数据结构对数据进行排序。

使用堆进行排序过程如下：

1. 将数列的数字依次添加到堆中；
2. 依次循环取出堆顶数字；
3. 取出数字的顺序即为排序后的顺序，完成整个排序。

构建堆有两种方案：

1. 将每个数字依次插入堆数组中，一边插入一边调整堆的结构，使其满足堆的要求；
2. 将整个数列的初始状态视作一棵完全二叉树，自底向上调整树的结构，使其满足堆的要求。

方案二更为常用，方案二无需使用额外空间。

初始化建堆的时间复杂度为 \(O(n)\)，重建堆的时间复杂度为 \(O(nlogn)\)，所以堆排序总的时间复杂度为 \(O(nlogn)\)。堆排序的空间复杂度为 \(O(1)\)，只需要常数级的临时变量。

代码实现

class Solution {
public:
    void heapSort(vector<int>& nums) {
        buildMaxHeap(nums);
        for (int i = nums.size() - 1; i > 0; i--) {
            swap(nums[0], nums[i]);
            maxHeapify(nums, 0, i);
        }
    }
    void buildMaxHeap(vector<int>& nums) {
        for (int i = nums.size() / 2 - 1; i >= 0; i--) {
            maxHeapify(nums, i, nums.size());
        }
    }
    void maxHeapify(vector<int>& nums, int root, int heapSize) {
        int left = root * 2 + 1;
        int right = left + 1;

        int largest = root;
        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }

        if (largest != root) {
            swap(nums[largest], nums[root]);
            maxHeapify(nums, largest, heapSize);
        }
    }
};