堆排序
什么是堆
堆是一种叫做完全二叉树的数据结构，可以分为大顶堆和小顶堆。
堆的分类
大顶堆：每个结点的值都大于或者等于他的左右结点的值
小顶堆：每个结点的值都小于或者等于他的左右结点的值
下标为 i 的父节点下标: (i - 1) / 2
下标为 i 的左孩子下标: i * 2 + 1
下标为 i 的右孩子下标: i * 2 + 2
排序思想
1、首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
2、将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n - 1
3、将剩余的n - 1个数再构造成大根堆，再将顶端数与n -1位置交换，如此反复执行，便能得到有序数组
注意：升序用大根堆，降序用小根堆
因为大根堆每次都将最大的数交换到数组末尾
小顶堆每次都将最小的数交换到数组末尾
维护堆
如果二叉树中的某个结点不满足堆的性质，就要对其进行维护
以大顶堆为例：
如果发现一个结点比他的左孩子或者右孩子小，就将该节点与值最大的孩子结点进行交换
/*
维护堆num:表示存储堆的数组n 数组长度i 待维护结点的下标
*/
void hepify(vector<int>& nums, int n, int i) {int largest = i;int lson = i * 2 + 1;int rson = i * 2 + 2;if (lson < n && nums[largest] < nums[lson])largest = lson;if (rson < n && nums[largest] < nums[rson])largest = rson;//有个孩子比该结点大if (largest != i) {swap(nums[i], nums[largest]);//调整后，下面的结点可能依旧不满足，要递归执行hepify(nums, n, largest);}
}
构建堆
1、从最后一个子树开始，从后往前调整
2、每次调整，从上往下调整
3、调整为大根堆
首先将给定的一个无序队列看成一个堆结构，一个没有规则的二叉树，将序列里的值按照从上往下，从左到右依次填充到二叉树中
如何构建堆呢？ 找到最后一个非叶子结点，也就是下标为arr.size() / 2 - 1的结点，比较它的左右节点中最大的一个的值，是否比他大，如果大就交换位置。
此时就构建出来一个大顶堆。
接下来进行排序
因此可以归纳出堆排序的步骤：
1、将无序数组构建成堆
2、循环删除堆顶元素，移动集合尾部，调节堆产生新的堆顶
void heap_sort(vector<int>& nums, int n) {//建堆//i = n / 2 - 1是最后一个非叶子结点的下标//依次调整非叶子结点的下标，直到堆顶为止for (int i = n / 2 - 1; i >= 0; i--) {hepify(nums, n, i);}//排序for (int i = n - 1; i > 0; i--) {swap(nums[i], nums[0]);hepify(nums, i, 0);}}
完整代码
/*
维护堆num:表示存储堆的数组n 数组长度i 待维护结点的下标
*/
void hepify(vector<int>& nums, int n, int i) {int largest = i;int lson = i * 2 + 1;int rson = i * 2 + 2;if (lson < n && nums[largest] < nums[lson])largest = lson;if (rson < n && nums[largest] < nums[rson])largest = rson;//有个孩子比该结点大if (largest != i) {swap(nums[i], nums[largest]);//调整后，下面的结点可能依旧不满足，要递归执行hepify(nums, n, largest);}
}void heap_sort(vector<int>& nums, int n) {//建堆//i = n / 2 - 1是最后一个非叶子结点的下标//依次调整非叶子结点的下标，直到堆顶为止for (int i = n / 2 - 1; i >= 0; i--) {hepify(nums, n, i);}//排序for (int i = n - 1; i > 0; i--) {swap(nums[i], nums[0]);hepify(nums, i, 0);}}int main() {vector<int> nums{ 30, 24, 5, 58, 18, 36, 12, 42, 39 };cout << "排序前：";for (int num : nums)cout << num << " ";cout << endl;heap_sort(nums, nums.size());cout << "堆排序后：";for (int num : nums)cout << num << " ";cout << endl;
}结果：
排序前：30 24 5 58 18 36 12 42 39
堆排序后：5 12 18 24 30 36 39 42 58
)
