堆排序

时间复杂度为O(n)

void heapify(vector<int>& nums,int n,int i){
    int largest=i;//假设为父节点
    int lson=i*2+1;
    int rson=i*2+2;
    //找到最大值
    if(lson<n&&nums[lson]>nums[largest])
        swap(nums[lson],nums[largest]);
    if(rson<n&&nums[rson]>nums[largest])
        swap(nums[rson],nums[largest]);
    if(largest!=i){
        swap(nums[largest],nums[i]);
        heapify(nums,n,largest);
    }
}
void heap_sort(vector<int>& nums,int n){
    int i=0;
    //键堆,从下往上建,从父结点开始
    for(i=n/2-1;i>=0;i--){
        heapify(nums,n,i);
    }
    //排序
    for(int j=n-1;j>=0;j--){
        swap(nums[j],nums[0]);
        heapify(nums,j,0);
    }
}

假设当前节点的下标为i

父节点下标：(i/2)-1;

左孩子的下标：i*2+1;

右孩子的下标：i*2+2;