堆排复习

堆排实现：先实现大堆序，即根节点大于两个子节点，从最后一个非叶子节点开始检查（也可以直接从最后一个节点开始检查，浪费时间而已），判断该节点是否比两个子节点小，若小，与最大的子节点交换，这里交换完毕后需要递归更新交换后的节点是否依旧符合大堆序，依次遍历到根节点，则大堆序成立。然后将最大值交换到最末尾位置，递归更新根节点保证大堆序成立，直到所有数据排序完成。

```cpp
class Solution {
public:

void UpdateNode(vector<int> &nums,int nums_index,int end_index)
    {
        int left_index = 2 * nums_index + 1;
        int right_index = 2 * nums_index + 2;

if(left_index >= end_index) return; //没有左右子树（因为是满二叉树，没有左子树就不存在右子树）

int change_index = left_index; 
        if(right_index < end_index && nums[right_index] > nums[left_index])
        {
            change_index = right_index;     //找到左右子树中最大的值
        }

if(nums[nums_index] < nums[change_index])  //存在子节点值大于根节点值
        {
            std::swap(nums[nums_index],nums[change_index]);
            UpdateNode(nums,change_index,end_index);  //递归修正子节点 保持堆排格式
        }
    }

//创建堆 格式为 根节点的值一定比左右子树的值大
    void createDeap(vector<int> &nums,int end_index)
    {
        //从第一个非叶子节点开始向上遍历
        int start_index = end_index / 2 - 1;
        for (int i = start_index; i >= 0; -- i)
        {
            UpdateNode(nums,i,end_index);
        }
    }

vector<int> sortArray(vector<int>& nums) {
        if(nums.empty()) return nums;
        createDeap(nums,(int)nums.size());  //创建堆

for(int i = (int)nums.size() - 1; i > 0; --i)  //依次交换最大值到末尾
        {
            std::swap(nums[0],nums[i]);
            UpdateNode(nums,0,i);   //更新交换后的根节点 保证大堆序
        }

return nums;
    }
};
```