堆排序

堆排序的过程为

建堆 从最后一个非叶子节点（对于节点编号为0~n-1的树，最后一个非叶子节点为n/2-1)，按照堆的定义调整堆（即选择当前这个节点两个儿子节点(i*2+1,i*2+2)中的最大值，然后交换当前节点和该最大值节点）

倒着做可以保证当前处理节点的子树都是符合堆的特性的

这样子可以保证只有当前处理的这个节点不符合堆的特性

如

显然除了根节点以外都已调整好，每次调整时，由于选择的是最大的节点，显然，换上去的节点大于左右两棵子树中的所有节点，这样子唯一不符合堆结构的节点就被交换到某棵子树中。

如此调整，可以保证只需要调整一条从该节点出发到叶节点的路径

若只调节当前三个节点的位置，在上图这种情况显然是无法恢复成堆的

当建堆完成后，每次将根节点和最后一个节点交换，此时最后一个节点就是最大的节点（已经完成排序），将树的最大节点-1，后重新按上述方式从根开始调整这颗树，最后得到的序列就是排好序的

代码(leetcode912):

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
class Solution {
public:
    void buildHeap(vector<int>& a){
        int len=a.size();
        for(int i=len/2-1;i>=0;i--){
            adjustHeap(a,i,len);
        }
    }
    void adjustHeap(vector<int>& a,int fa,int size){
        int tmp=a[fa];
        for(int i=(fa<<1)+1;i<size;i=i*2+1){
            if(i+1<size&&a[i+1]>a[i])i++;
            if(a[i]>tmp){
                a[fa]=a[i];
                fa=i;
            }
            else break;
        }
        a[fa]=tmp;
    }
    vector<int> sortArray(vector<int>& nums) {
        buildHeap(nums);
        int len=nums.size();
        for(int i=len-1;i>=1;i--){
            swap(nums[i],nums[0]);
            adjustHeap(nums,0,i);
        }
        return nums;
    }
};
int main(){
    Solution s;
    vector<int> a={-4,0,7,4,9,-5,-1,0,-7,-1};
    s.sortArray(a);
}